Skip to main content

Currently Skimming:

4 Quantum Computing's Implications for Cryptography
Pages 95-112

The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.


From page 95...
... Practical quantum computing at scale would have a significant impact on several cryptographic algorithms currently in wide use. This section explains what these algorithms are for and how they will be affected by the advent of large-scale quantum computers.
From page 96...
... This type of replacement has already had to be done when a widely deployed hash function, called MD5, was found to be vulnerable to attack. While alternatives were deployed rapidly, it took over a decade for the vulnerable hash function to be completely removed from use.1 This chapter explains the key cryptographic tools deployed throughout today's conventional computing systems, what is known about their susceptibility to attack via a quantum computer, alternative classical cryptographic ciphers expected to be resilient against quantum attack, and the challenges and constraints at play in changing a widely deployed cryptographic regime.
From page 97...
... This way, security of key exchange and security of symmetric encryption are comparable. The impact of a quantum computer: Asymmetric cryptographic algorithms used in key exchange protocols appear to be the most vulnerable to compromise by known quantum algorithms, specifically by Shor's algorithm.
From page 98...
... TABLE 4.1  Literature-Reported Estimates of Quantum Resilience for Current Cryptosystems, under Various 98 Assumptions of Error Rates and Error-Correcting Codes Quantum Time Algorithm # Logical # Physical Required Quantum-Resilient Key Security Expected to Defeat Qubits Qubits to Break Replacement Cryptosystem Category Size Parameter Cryptosystem Required Requireda Systemb Strategies AES-GCMc Symmetric 128 128 Grover's algorithm 2,953 4.61 × 106 2.61 × 1012 encryption 192 192 4,449 1.68 × 107 years 256 256 6,681 3.36 × 107 1.97 × 1022 years 2.29 × 1032 years RSAd Asymmetric 1024 80 Shor's algorithm 2,050 8.05 × 106 3.58 hours Move to NIST encryption 2048 112 4,098 8.56 × 106 28.63 hours selected PQC 4096 128 8,194 1.12 × 107 229 hours algorithm when available ECC Asymmetric 256 128 Shor's algorithm 2,330 8.56 × 106 10.5 hours Move to NISTDiscrete-log encryption 384 192 3,484 9.05 × 106 37.67 hours selected PQC probleme-g 521 256 4,719 1.13 × 106 55 hours algorithm when available SHA256h Bitcoin N/A 72 Grover's Algorithm 2,403 2.23 × 106 1.8 × 104 mining years PBKDF2 with Password N/A 66 Grover's algorithm 2,403 2.23 × 106 2.3 × 107 Move away from 10,000 iterationsi hashing years password-based authentication
From page 99...
... Gheorghiu, 2018, "A Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions -- ­ mprovements," I Global Risk Institute, https://globalriskinstitute.org. i The time estimate for password hashing is based upon the time estimate (as it appears in the preceding row of the table)
From page 100...
... The impact of a quantum computer: AES is a perfect fit for Grover's algorithm, which was discussed in the previous chapter. The algorithm can identify the secret key over the entire 128-bit key space of AES-GCM in time proportional to the square root of 2128 -- namely, time 264.
From page 101...
... 4.1.3 Certificates and Digital Signatures Digital signatures are an important cryptographic mechanism used to verify data integrity. In a digital signature system, the signer has a secret signing key, and the signature verifier has a corresponding public key, another example of asymmetric encryption.
From page 102...
... 4.1.4 Cryptographic Hash Functions and Password Hashing The final cryptographic primitive discussed here enables one to compute a short message digest, called a hash, from an arbitrarily long message. The hash function can take gigabytes of data as input and output a short 256-bit hash value.
From page 103...
... steps, which at the speed of a modern classical processor takes only a few seconds. However, the need for QEC for deploying Grover's algorithm again suggests that, with current error correction algorithms (and reasonable assumptions about error rates and architectures)
From page 104...
... For example, if physical gate error rates of 10–6 were to be achieved (e.g., by topological qubits) , and the other assumptions remain the same, then the number of physical qubits required to break RSA-4096 would drop to 6.7 × 106, and the time would drop to 190 hours.
From page 105...
... Like all cryptography, the hardness of these problem cannot be proved, and must continue to be evaluated over time to ensure that new algorithmic approaches do not weaken the cypher. 4.3.1 Symmetric Encryption and Hashing Post-quantum secure symmetric encryption and hash functions are obtained by simply increasing the encryption key size or hash output size.
From page 106...
... To experiment with lattice-based systems, cryptographers developed sev eral concrete schemes, such as New-Hope2 and Frodo.3 Google recently experi­ mented with deploying the New-Hope system in the Chrome browser.4 They report that the system adds less than 20 milliseconds per key exchange for 95 percent of Chrome users. While this additional delay is undesirable, the experiment shows that there is no significant impediment to deploying post-quantum key exchange based on lattice systems.
From page 107...
... Since the additional traffic is the primary reason for the delay, this candidate may outperform other candidates in real-world Internet settings. This key exchange mechanism is based on beautiful mathematical tools developed to study elliptic curves.
From page 108...
... Finding: While the potential utility of Shor's algorithm for cracking deployed cryptography was a major driver of early enthusiasm in quantum computing research, the existence of cryptographic algorithms that are believed to be quantum-resistant will reduce the usefulness of a quantum computer for cryptanalysis and thus will reduce the extent to which this application will drive quantum computing R&D in the long term. 4.4 PRACTICAL DEPLOYMENT CHALLENGES It is important to remember that today's encrypted Internet traffic is vulnerable to an adversary who has a sufficiently large quantum computer running quantum error correction.
From page 109...
... After this is done, sensitive data in corporate and government repositories must be reencrypted, and any copies encrypted under the previous paradigm need to be destroyed -- especially given that some organizations rely upon merely deleting encryption keys as a substitute for destroying files, which will not help against an attack by a quantum computer. Vulnerable public-key certificates must be reissued and redistributed, and any documents that must be certified from official sources must be re-signed.
From page 110...
... Once these three things have been identified, the required timing can be computed using a simple formula3 illustrated in Figures 4.1 and 4.2, where: • X is the "security shelf life" (the longest protection interval we care about, assuming that the data is protected starting today) • Y is the "migration time" (the time it takes to design build, and deploy the new infrastructure)
From page 111...
... . In this gloomier scenario, illustrated in Figure 4.2, there is no safety margin; if a large quantum computer goes online 15 years from today, sensitive data will remain at risk of compromise, with no effective protection technology available, for 3 years -- even if the work to replace our public-key cryptographic infrastructure begins today.
From page 112...
... Assuming a security shelf life of 7 years as in the previous scenario, the earliest safe date for the introduction of a quantum computer capable of breaking RSA 2048 is about 2040 -- if the work of replacing today's cryptographic libraries and crypto-dependent applications is begun as soon as NIST finishes its selection process. To put this another way, if a fault-tolerant quantum computer with 2,500 logical qubits is built any time in the next 25 years, some data will likely be compromised -- even if work on the cryptographic fallout is begun today and continued diligently during the entire interval.


This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More information on Chapter Skim is available.