Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

4 Quantum Computingâs Implications for Cryptography Increases in computational power are desirable, except for applications that rely upon the computational complexity of certain operations in order to function, which is the case in cryptography. Cryptography is an indispensable tool used to protect information in computer systems and it is used widely to protect communications on the Internet. 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. Given the computing power that such a quantum computer is expected to have, the cryptography research community has developed and is continuing to develop post-quantum (or âquantum-safeâ) cryptographic algorithms. These are candidate cryptographic algorithms that run on a classical computer and are designed to remain secure even against an adversary who has access to a scalable, fault-tolerant quantum computer. While it may not be obvious to the general public, cryptography underlies many interactions and transactions on the World Wide Web. As one example, most connections to Web sites use âhttps,â a Web protocol that encrypts both the information a user sends to a Web site, and the information that the Web site sends backâfor example, credit card information, bank statements, and e-mail. Another example is protecting stored passwords in a computer system. Passwords are stored in a form that allows the computer system to check that a user-entered password is correct, without storing the actual password. Protecting stored passwords in this way prevents passwords from being âstolenâ from the computer system in case of a security breach. In todayâs Web-based world, it is relatively easy for a large company like Google to experiment with new types of cryptography. A company like Google can make changes to its browser and its servers to add support for a new protocol: when a Google browser connects to a Google server, it can elect to use the new protocol. However, removing an existing protocol is much harder, since before this can be done, all of the machines in the world that rely upon the old protocol must be updated to use the alternative protocol. 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. 4.1 CRYPTOGRAPHIC ALGORITHMS IN CURRENT USE Creating a secure communication channel between two people is usually done as a two-step process: two people are given a âshared secret keyâ in a process called âkey exchange,â and then this shared secret key is used to encrypt their communication so it cannot be understood (decrypted) by 1 The attack on MD5 was discovered by Wang in 2005. Only in 2014 did Microsoft release a patch to disable MD5: https://docs.microsoft.com/en-us/security-updates/SecurityAdvisories/2014/2862973. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-1

anyone without the secret key. The message encryption is called âsymmetric encryption,â since both parties used the same shared secret key to encrypt and decrypt the communications traffic. 4.1.1 Key Exchange and Asymmetric Encryption The first step in encrypting communications between two partiesâin this example, called Alice and Bobâis for them to obtain a shared (symmetric) key that is known to them but to no one else. To establish this shared key, the two parties engage in a key exchange protocol. The most widely used key exchange protocol, called the Transport Layer Security (TLS) handshake, is used to protect Internet traffic. During a key exchange protocol, the parties send a sequence of messages to each other. At the end of the protocol, they obtain a shared secret key that both of them know, but that no one else knows, including any adversary. This key can then be used for exchanging data securely using a symmetric encryption algorithm, which is discussed in Section 4.1.2. Key exchange protocols rely upon the assumption that certain algebraic problems are intractable. One such problem that is widely used in practice is called the âdiscrete-log problem on elliptic curves.â For the purpose of this discussion, it suffices to say that an instance of this problem of size n bits can be solved classically in exponential time in n, or more precisely in time 2n/2. No better classical algorithm is known (although it has not been proven that none exists). In practice, one typically sets the key size as 256, meaning that the best-known classical attack on the key exchange protocol runs in time 2256/2 = 2128âthe same as the time required to attack 128-bit AES-GCM. 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. Because Shorâs algorithm provides an exponentially faster method for solving the discrete-log problem and for the problem of factoring large integers, an adversary able to deploy it on a quantum computer could break all the key exchange methods currently used in practice. Specifically, key exchange protocols based on variants of the Diffie-Hellman and the RSA protocols would be insecure. To break RSA 1024 would require a quantum computer that has around 2,300 logical qubits, and even with the overhead associated with logical qubits, this algorithm could likely be carried out in under a day (see Table 4.1). Because of the seriousness of this potential compromise, the National Institute of Standards and Technology (NIST) in 2016 began a process that is expected to last six to eight years [1] to select and standardize replacement asymmetric cryptographic algorithms that are quantum secure. Potential replacements to currently deployed key exchange systems are discussed later in this chapter. 4.1.2 Symmetric Encryption Once Alice and Bob have established their shared secret key, they can use it in a âsymmetric cipherâ to ensure that their communication stays private. A widely used encryption method called the Advanced Encryption Standard-Galois Counter Mode (AES-GCM) has been standardized for this purpose by NIST. In its simplest form, this encryption method is based on a pair of algorithms: an âencryption algorithmâ and a âdecryption algorithmâ that encode and decode a message. The encryption algorithm takes as input a key and a message, scrambles the bits of the message in a very precise way, and outputs a âciphertext,â an encoded form of the message that looks like random bits. The decryption algorithm takes as input a key and a ciphertext, uses the key to reverse the scrambling and output a message. AES-GCM is designed so that analysis of the ciphertext provides no information about the message. AES-GCM supports three key sizes: 128 bits, 192 bits, and 256 bits. Suppose that an adversary, Eve, intercepts a ciphertext that she wants to decrypt. Furthermore, suppose Eve knows the first few characters in the decrypted message, as is common in Internet protocols where the first few characters are a fixed message header. When using a 128-bit key in AES-GCM, Eve can try all 2128 possible keys by PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-2

exhaustive search until she finds a key that maps the first bytes of the given ciphertext to the known message prefix. Eve can then use this key to decrypt the remainder of the intercepted ciphertext. For a 128-bit key, this attack takes 2128 trials, which even at a rate of a 1018 (one quintillion) trials per secondâ which is faster than even a very large custom-built AES computer would runâwill still take 1013 (ten trillion) years. For this reason, AES-GCM is frequently used with a 128-bit key. Longer keys, 192-bits and 256-bits, are primarily used for high-security applications where users are concerned about preprocessing attacks or potential undiscovered weaknesses in the AES-GCM algorithm that would enable a faster attack. 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. Running the algorithm on a quantum computer is likely to require around 3,000 logical qubits and extremely long decoherence times. How long would a quantum computer take to run the 264 steps of Groverâs algorithm, called Grover steps, to break AES-GCM? That is hard to answer today, since it depends on how long a quantum computer takes to execute each Grover step. Each Grover step must be decomposed into a number of primitive operations to be implemented reversibly. The actual construction of the quantum circuit for each Grover step can substantially increase the number of qubits and coherence times required for physical implementation. Using classical hardware, one can build a special purpose circuit that tries 109 keys per second. Assuming a quantum computer can operate at the same speed, it would need about 600 years to run Groverâs algorithm for the necessary 264 steps. It would therefore take a large cluster of such quantum computers to crack a 128-bit key in a month. In fact, this is an overly optimistic estimate, because this type of quantum computer requires logical qubits; this not only greatly increases the number of physical qubits required, but, as described in Section 3.2, operations on logical qubits require many physical qubit operations to complete. This overhead is high for ânon-Cliffordâ quantum gates, which are common in this algorithm. As Table 4.1 shows, assuming 100-nanosecond gate times and current algorithms for error correction, a single quantum computer would require more than 1012 years to crack AES-GCM. Even if a computer existed that could run Groverâs algorithm to attack AES-GCM, the solution is quite simple: increase the key size of AES-GCM from 128-bit to 256-bit keys. Running Groverâs attack on a 256-bit key is effectively impossible, since it requires as many steps as a classical attack on a 128-bit key. Transitioning to a 256-bit key is very practical and can be put to use at any time. Hence, AES-GCM can be easily made secure against an attack based on Groverâs algorithm. However, AES-GCM was designed to withstand known sophisticated classical attacks, such as linear and differential cryptanalysis. It was not designed to withstand a sophisticated quantum attack. More precisely, it is possible that there is some currently unknown clever quantum attack on AES-GEM that that is far more efficient than Groverâs algorithm. Whether such an attack exists is currently an open problem, and further research is needed on this important question. If a sophisticated quantum attack existsâone that is faster than exhaustive search using Groverâs algorithmâthen increasing the AES- GCM key size to 256 bits will not ensure post-quantum security and a replacement algorithm for AES- GCM will need to be designed. 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. The signer signs a message using its secret key. Anyone can verify the signature using the corresponding public key. If a message-signature pair is valid, then the verifier has some confidence that the message was authorized by the signer. Digital signatures are used widely, as illustrated in the following three examples. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-3

First, digital signatures are necessary for establishing identity on the Internet using a digital certificate. Here, a certificate authority (CA) uses its secret signing key to issue an identity certificate to an individual or an organization. A certificate is a statement that binds an identity, such as nas.edu, to a cryptographic key. Anyone can verify a certificate, but only the CA can issue a certificate, by digitally signing it using a secret signing key. An adversary who can forge the CAâs signature can, in principle, masquerade as any entity. A second application for digital signatures is in payment systems, such as credit card payments or a cryptocurrency such as Bitcoin. With these systems, a payer who wants to make payments holds a secret signing key. When making a payment, the payer signs the transaction details. The signature can be verified by anyone, including the payee and all relevant financial institutions. An attacker who can forge signatures can effectively spend other peopleâs funds. For a third example, consider the verification of software authenticity. Here, a software vendor uses its secret signing key to sign software and software updates that it ships. Every client verifies these signatures before installing the software, as they do with subsequent software updates. This ensures that clients know the software provenance and do not install software that has been tampered with or malware created and distributed by malicious actors. An attacker who could forge signatures could distribute malicious software to unsuspecting clients, who might install it thinking that it is authentic. The two most widely used signature algorithms are called RSA and ECDSA.2 Roughly speaking, one algorithm is based on the difficulty of factoring large integers, and the other is based on the same discrete log problem used for key exchange. The parameters for both systems are chosen so that the best- known classical attacks run in time 2128. The impact of a quantum computer: An adversary who has access to a quantum computer capable of executing Shorâs algorithm would have the ability to forge both RSA and ECDSA signatures. This adversary would be able to issue fake certificates, properly sign malicious software, and potentially spend funds on behalf of others. The attack is worse than just forging signatures; Shorâs algorithm allows attackers to recover private keys, which facilitates forging signatures but also eliminates the security of all other uses of the keys. Fortunately, there are several good candidate signature schemes that are currently believed to be post-quantum secure, as discussed at the end of this chapter. 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. There are many desirable properties that we might want hash functions to satisfy. The simplest is called âone-wayness,â or âcollision-resistance,â which means that for any given hash output value T, it should be difficult to find an input message that would yield that hash. Hash functions are used in many contexts; a simple example is their use in password management systems. A server that authenticates user passwords usually stores in its database a one-way hash of those user passwords. This way, if an attacker steals the database, it may be difficult for the attacker to recover the cleartext passwords. Currently, the most commonly used hash function is called SHA256. It outputs a 256-bit hash value no matter how large the input is. This hash function is the basis of many password authentication systems. To be precise, the actual hash function used to hash passwords is derived from SHA256 via a construction called PBKDF2 [2]. The impact of a quantum computer: A hash function that produces 256-bit outputs is not expected to be threatened by quantum computing. Even using Groverâs algorithm, it is currently believed to be essentially impossible (with a depth on the order of 2144 T gates on 2400 logical qubits) to break a hash function like SHA256. However, âpassword hashingâ is at a higher risk because the space of user passwords is not very large. The set of all 10-character passwords is only about 266 passwords. An 2 The former is named after its inventors, Rivest, Shamir, and Adelman. The latter stands for âelliptic curve digital signature algorithm.â PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-4

exhaustive search over a space of this size using a cluster of classical processors is possible, but very costly. Using Groverâs algorithm, the running time shrinks to only 233 (about 10 billion) 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), the time required for this attack is still too long to be practical, at more than 107 years, although the time frame could be reduced through reduction of QEC overheads. If QEC is improved to the point where Groverâs algorithm becomes a threat to password systems, then there will be a need to move away from password authentication. Other authentication methods, which do not rely on passwords or other static values that need to be stored in hashed form, have been developed and are being adopted in some applications. These methods include biometric authentication, cryptographic one-time values, device identification, and others. The development of quantum computers may further motivate the deployment of such systems. Another defense is to harden password management systems using secure hardware [3], as already implemented by major Web sites. Another popular application of hash functions is called proof-of-work, used in many crypto currencies such as Bitcoin and Ethereum. Blocks of Bitcoin transactions are validated every 10 minutes by a process in which âminersâ solve a certain computation challenge; the first miner to solve the problem is paid by the cryptocurrency system. Groverâs algorithm would be suited to solving a Bitcoin challenge. However, as the second to last row in Table 4.1 shows, the overhead of implementing Groverâs algorithm using physical qubits to solve the proof-of-work challenge is currently estimated to require well over 10 minutes, which would make the attack a nonthreat to the current Bitcoin ecosystem. If the overheads required for this implementation were significantly reduced, there could be some risk if or when fault- tolerant quantum computers become available; Bitcoin would thus also need to transition to a post- quantum secure digital signature system to avoid bitcoin theft. 4.2 SIZING ESTIMATES A critical question for understanding the vulnerability of cryptographic tools is: What scale of a quantum computer would be required to defeat the cipher? The answer to this question is expected to vary with the details of how the quantum algorithm is deployed. Nonetheless, a rough approximation of the number of qubits required for defeating various protocols for a given key size is provided in Table 4.1. This table also estimates the number of physical qubits required (assuming an effective error rate of 10-5), and the time required for the algorithmâs execution, using a surface code for quantum error correction and a surface code measurement cycle time of 100 nanoseconds. These assumptions for gate fidelity and gate speed are well beyond the capabilities of multiqubit systems in 2018. The table clearly shows that the major threats posed by a sophisticated quantum computer are breaking key exchange and digital signatures. While these figures reflect the current state of knowledge, the committee cautions the reader that these assessments are based upon quantum algorithms that are currently known, as well as implicit assumptions about the architecture and error rates of a quantum computer. Advances in either area have the potential to change timings by orders of magnitude. 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. Similarly, if the assumptions are not achieved, then implementing these algorithms might not be possible or might come at a greater costâfor example, if physical gate error rates of only 10-4 are achieved, then the number of physical qubits required to break RSA-4096 would increase to 1.58 Ã 108 and the time required would increase to 280 hours [4]. It is also possible that new algorithms could be developed (or could already have been developed outside of the public sphere) that would present different attack vectorsâfor that matter, the same can also be said about potential alternative classical attacks. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-5

TABLE 4.1 Literature-Reported Estimates of Quantum Resilience for Current Cryptosystems, under Various Assumptions of Error Rates and Error-Correcting Codes Quantum Algorithm # Time Quantum- Expected to Logical # Physical Required to Resilient Cryptos Key Security Defeat Qubits Qubits Break Replacement ystem Category Size Parameter Cryptosystem Required Requireda Systemb Strategies AES- Symmetric 128 128 Groverâs 2,953 4.61 Ã 106 2.61 Ã 1012 GCM encryption 192 192 algorithm 4,449 1.68 Ã 107 yrs [5] 256 256 6,681 3.36 Ã 107 1.97 Ã 1022 yrs 2.29 Ã 1032 yrs RSA [6] Asymmetric 1024 80 Shorâs 2,290 2.56 Ã 106 3.58 hours Move to encryption 2048 112 algorithm 4,338 6.2 Ã 106 28.63 hours NIST-selected 4096 128 8,434 1.47 Ã 107 229 hours PQC algorithm when available ECC Asymmetric 256 128 Shorâs 2,330 3.21 Ã 106 10.5 hours Move to Discrete encryption 386 192 algorithm 3,484 5.01 Ã 106 37.67 hours NIST-selected -log 512 256 4,719 7.81 Ã 106 95 hours PQC problemc algorithm [7,8] when available SHA256 Bitcoin N/A 72 Groverâs 2,403 2.23 Ã 106 1.8 Ã 104 [9] mining Algorithm years PBKDF Password N/A 66 Groverâs 2,403 2.23 Ã 106 2.3 Ã 107 Move away 2 with hashing algorithm years from 10,000 password- iteration based sd authentication a These are rough estimates. The number of physical qubits required depends on several assumptions, including the underlying architecture and error rates. For these calculations, assumptions include a two-dimensional (2D) lattice of qubits with nearest neighbour interactions, an effective error rate of 10-5, and implementing the surface code. b These are rough estimates. In addition to the assumptions associated with estimation of the number of physical qubits required, a quantum computer with gates operating at a 10 MHz frequency was assumed. c The values given are for the NIST P-256, NIST P-386, and NIST P-521 curves. d The time estimate for password hashing is based upon the time estimate (as it appears in the preceding row of the table) for SHA256, which is often used iteratively in PBKDF2, a password hashing algorithm. Assuming 10,000 iterations of SHA256 (a common deployment practice) would take 10,000 times as long as a single iteration. The classical search space of one cycle is 266, which implies a running time for Grover of 233, or one-eighth that required for breaking SHA256 in Bitcoin. Thus, the current estimate of 2.3 Ã 107 years is obtained by multiplying the value obtained for SHA256 by 10,000 and dividing by 8. NOTE: These estimates are highly dependent on the underlying assumptions,and are subject to update in the final report. 4.3 POST-QUANTUM CRYPTOGRAPHY The cryptographic research community has been working to develop replacement algorithms that are expected to be secure against an adversary with access to a large-scale quantum computer. These replacement algorithms, when standardized, will be executable on off-the-shelf classical processors. Their security relies on mathematical problems that are believed to be intractable even for a large-scale quantum computer. These algorithms, currently being evaluated by NIST, are thus expected to remain PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-6

secure even after large-scale quantum computers are widely available. 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. Adequate solutions already exist, and the primary remaining challenge is to verify, through additional research to identify possible quantum attacks, that the standardized schemes, such as 256-bit AES-GCM and SHA256, are indeed secure against an adversary who has access to a quantum computer. Problems where an increase in the size of the hashed data is not possible (or where the hashed dataâs entropy does not increase much even if its size is increased), like password systems, would be difficult to secure in a world with fast quantum computers. If a quantum computer was as fast as a modern classical processor in logical operations per second, thanks to Groverâs algorithm, a quantum computer would likely be able to identify the 10-character password in a few seconds. While the need for extensive error correction would make this attack much slower in practice, the availability of low-overhead approaches would place passwords at risk. Defending against this threat requires either moving away from password authentication or using a hardware-based password hardening scheme, as mentioned earlier. 4.3.2 Key Exchange and Signatures The most significant challenges are post-quantum key-exchange and post-quantum digital signatures. For quantum resilience, existing schemes such as RSA and ECDSA will need to be abandoned and new systems will need to be designed. NIST has already initiated a Post-Quantum Cryptography project to facilitate this process, seeking proposals for new cryptographic algorithms [10]. In the first round of submissions, which ended in November 2017, NIST received over 70 submissions. The NIST process is scheduled to conclude by 2022-2024; its selections are likely to become frontrunners for broader standardizationâfor example, through the Internet Engineering Task Force (IETF), the International Organization for Standardization (ISO), and the International Telecommunication Union (ITU). Internet systems will likely begin incorporating post-quantum resistant cryptography once the NIST process concludes, if not sooner. Boxes 4.1 to 4.4 provide brief descriptions of a few candidate post-quantum key-exchange and signature systems, as well as pointing out some early experiments done with some of these systems. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-7

BOX 4.1 Post-Quantum Candidates: Lattice Systems A âlatticeâ is a discrete set of points in space that has the property that the sum of two points on the lattice is also on the lattice. Lattices come up naturally in several branches of mathematics and physics. One of the most well-known computational problems on lattices is to find a âshortâ vector in a given lattice. All current classical algorithms for this problem take exponential time in the dimension of the lattice, and there is some evidence to suggest that the problem also takes exponential time on a quantum computer.1 Over the past two decades, cryptographers constructed many cryptosystems that are secure assuming that this shortest vector problem (SVP) is hard. In particular, there are good candidate key-exchange and signature algorithms based on SVP. If indeed SVP is difficult to solve on a quantum computer, then these systems are expected to be post-quantum secure. To experiment with lattice-based systems, cryptographers developed several concrete schemes, such as New-Hope2 and Frodo.3 Google recently experimented 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. 1 O. Regev, 2009, âOn lattices, learning with errors, random linear codes, and cryptography,â Journal of the ACM (JACM) 56(6):34. 2 E. Alkim, T. PÃ¶ppelmann, and P. Schwabe, 2016, âPost-Quantum Key ExchangeâA New Hope,â USENIX Security Symposium on August 10-12, 2016, in Austin, TX. 3 J. Bos, C. Coestello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, and D. Stebila, 2016, âFrodo: Take Off the Ring! Practical, Quantum-Secure Key Exchange from LWE,â Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, October 24-28, 2016, in Vienna, Austria. 4 M. Braithwaite, 2016, âExperimenting with Post-Quantum Cryptography,â Google Security Blog, https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html. BOX 4.2 Post-Quantum Candidates: Coding-Based Systems Coding theory is the science of designing encoding schemes that let two parties communicate over a noisy channel. The sender encodes a message so that the receiver can decode even if bounded noise has been added by the channel. Over the years it has become apparent that certain encoding schemes are difficult to decode efficiently. In fact, for certain encoding schemes, the best decoding algorithm takes exponential time on a classical computer. Moreover, the decoding problem appears to be difficult even for a quantum computer. Cryptographers have been able to use this hard problem to construct secure cryptosystems, assuming that decoding the relevant codes is difficult. The most well studied system, called the McEliece cryptosystem, 1 can be used for post-quantum key exchange. Recently, practical variants of this system, such as CAKE,2 have emerged. 1 D.J. Bernstein, T. Lange, and C. Peters, 2008, Attacking and defending the McEliece cryptosystem, Post- Quantum Cryptography, vol. 5299:31-46. 2 P.S.L.M. Barreto, S. Gueron, T. Gueneysu, R. Misoczki, E. Persichetti, N. Sendrier, and J.-P. Tillich, 2017, âCAKE: Code-Based Algorithm for Key Encapsulation,â in M. OâNeill (eds) Cryptography and Coding: 16th IMA International Conference, IMACC 2017, Oxford, UK, December 12-14, 2017, Proceedings: 207-226. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-8

BOX 4.3 Post-Quantum Candidates: Supersingular Isogenies The Google experiment with the New-Hope lattice-based key exchange suggests that the primary reason for the 20 millisecond delay is due to the extra traffic generated by the key exchange protocol. Building on this observation, a recent post-quantum key exchange candidate1 generates far less traffic than any other candidate, but it requires more computing time at both ends. 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. While there is no known quantum attack on the system, it is based on a computational problem whose quantum difficulty has only begun to be explored recently. More research is needed to gain confidence in the post-quantum security of this candidate. 1 C. Costello, P. Longa, and M. Naehrig, 2016, âEfficient Algorithms for Supersingular Isogeny Diffie- Hellman,â in M. Robshaw and J. Katz (eds.), Advances in CryptologyâCRYPTO 2016. CRYPTO 2016, Lecture Notes in Computer Science, vol. 9814, Springer, Berlin, Heidelberg. BOX 4.4 Post-Quantum Candidates: Hash-Based Signatures Post-quantum secure digital signatures have been around since the 1980s. These systems are based on standard hash functions, and there is little doubt about their post-quantum security, when using a secure hash function. The downside of these schemes is that they generate relatively long signatures, and therefore can be used only in certain settings. One such setting is signing a software package or a software update. Because software packages tend to be large, the added length of the signature is of little consequence. Given the high confidence in the post-quantum security of these systems, it is likely that software vendors will transition away from RSA and elliptic curve digital signature algorithm (ECDSA) to hash-based signatures for software signing. Several concrete proposals and drafts for standardization already exist, such as the Leighton-Micali signature scheme (LMSS). 1 1 T. Leighton and S. Micali, 1995, âLarge Provably Fast and Secure Digital Signature Schemes from Secure Hash Functions,â U.S. Patent 5,432,852. Finding: While the potential utility of Shorâs algorithm for cracking deployed cryptographic algorithms 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. In particular, all encrypted data that is recorded today and stored for future use, will be cracked once a large-scale quantum computer is developed. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-9

Finding: There is strong commercial interest in deploying post-quantum cryptography even before such a quantum computer has been built. Companies and governments cannot afford to have their private communications decrypted in the future, even if that future is 30 years away. For this reason, there is a need to begin the transition to post-quantum cryptography as soon as possible. Realistically, completing the transition to Internet-wide post-quantum cryptography will be a long and difficult process. Some computer systems remain operational for a very long time. For example, computer systems in cars sold today will still be on the road in 15, and perhaps even 20 years. A quantum-vulnerable algorithm can be deprecated only once the vast majority of Internet systems are updated to support new algorithms. Once a major site like Google deprecates an algorithm, old devices that support only that algorithm can no longer connect to Google. A good example of this timeline is the long process of deprecating the SHA1 hash function and the transition to SHA256. The SHA1 function was considered to be insecure since 2004. However, it took many years to disable it. Even as of 2018, it is still not universally decommissionedâsome old browsers and servers still do not support SHA256. The transition from SHA1 to SHA256 provides a map for the steps required to transition to post- quantum cryptography. First, post-quantum cryptographic algorithm standards for key-exchange and signatures will need to be developed and ratified. After adoption as an official standard, the new standard algorithms must be implemented in a wide variety of computer languages, popular programming libraries, and hardware cryptographic chips and modules. Then the new standard algorithms will need to be incorporated into encryption format and protocol standards such as PKCS#1, TLS, and IPSEC. These revised format and protocol standards will need to be reviewed and adopted by their respective standards committees. Then vendors will need to implement the new standards in hardware and software product updates. From there, it will likely take many years until the majority of Internet systems are upgraded to support the new standardsâand quantum-vulnerable algorithms cannot be disabled until their replacements are widely deployed. 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. Last, the signing and verification processes for all software code must be updated, and the new code must be re-signed and redistributed. This process probably cannot be completed in less than 20 years; the sooner it is begun, the sooner it will conclude [11]. Since the invention of a scalable general-purpose quantum computer would constitute a total, simultaneous, instantaneous, worldwide compromise of all of todayâs public-key cryptographic algorithms, quantum-resistant cryptographic algorithms would need to be designed, standardized, implemented, and deployed before the first quantum computer goes online. But in fact, the quantum- resistant infrastructure must be in place even before a quantum computer goes live, because encrypted (or signed) data needs to be protected for longer than an instant. For example, consider a companyâs 10Q filing. This quarterly tax document contains information that is sensitive until it is published; people who come into possession of a 10Q before it is public information know things about the companyâs financial condition that they could use to profit from insider trading (because the stock value will change once the 10Q information becomes public, and people who know the information in advance can predict the magnitude and direction of the change and buy or sell shares accordingly). A 10Q filing needs to stay secret for no more than three months; after the end of the quarter, it is filed and published, and the information is no longer sensitiveâso it does not need to be secret. So for a 10Q filing, the required âprotection intervalâ is three months. Now, consider a government classified document. Under the 50-year rule, the contents should not be made public for at least 50 years. Hence, the document must be encrypted with an encryption scheme that is expected to remain secure for at least 50 years. The required âprotection intervalâ is 50 years. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-10

Three pieces of information are necessary to determine when a quantum-resistant cryptographic infrastructure should be put in place: 1. When will the current cryptographic infrastructure fail? (That is, when would a quantum computer of sufficient sophistication to deploy Shorâs or Groverâs algorithms go live?) 2. How long does it take to design, build, and deploy the new quantum-resistant infrastructure? 3. Whatâs the longest protection interval of concern? 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) ï· Z is the âcollapse timeâ (the time it takes for a sufficiently large quantum computer to become operational, starting from today) FIGURE 4.1 Illustration of Moscaâs model for a safe transition to post-quantum cryptography, for one example with hypothetical time frames. SOURCE: Adapted from M. Mosca, 2015, âCybersecurity in an Era with Quantum Computers: Will We Be Ready?â IACR Cryptology ePrint Archive 2015:1075. The example in Figure 4.1 assumes that no quantum computer will exist for 15 years, that a quantum-resistant infrastructure can be designed, built, and deployed in only 3 years, and that the longest security shelf-life of concern is only 5 years. This optimistic scenario yields a safety margin of 7 years, suggesting that the start of earnest working on replacing our public-key cryptographic infrastructure could be delayed for several years. A less optimistic scenario would set migration time at 10 years (the pessimistic estimate for completion of NISTâs planned standardization interval of 2022-2024 plus up to 3 years for implementation and deployment), and security shelf life at 7 years (a common legally required retention interval for many kinds of business records). 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. 3 This formula was introduced by committee member Michele Mosca: M. Mosca, 2015, âCybersecurity in an Era with Quantum Computers: Will We Be Ready?â IACR Cryptology ePrint Archive 2015:1075. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-11

FIGURE 4.2 Example illustration of Moscaâs model of a cryptographic transition timeline that is too long to ensure the desired level of security in deployed protocols. SOURCE: Adapted from M. Mosca, 2015, âCybersecurity in an Era with Quantum Computers: Will We Be Ready?â IACR Cryptology ePrint Archive 2015:1075. The most realistic scenario is even more pessimistic. As noted in the preceding section, NISTâs current schedule will result in the selection of a quantum-safe cryptographic algorithm suite around 2022- 2024. Past experience with replacing the data encryption standard (DES) symmetric cryptosystem and various hash functions (SHA-1, MD5) suggests that the minimum time required to replace a widely deployed cryptographic algorithm, including retiring most consequential implementations of the broken algorithm, is about 10 years after design and standardization of the new algorithms are complete. 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. Much depends upon when such a device will come on the scene. The following two chapters provide a closer view of the current status of efforts to build a large-scale, fault-tolerant quantum computer. Chapter 5 describes progress in constructing quantum computing hardware and control systems, and Chapter 6 examines the software and architectureâincluding the classical co-processingâ that will be required to implement algorithms on a mature device. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-12

NOTES [1] âPost-Quantum Cryptography,â National Institute of Standards and Technology, last updated May 29, 2018, https://csrc.nist.gov/projects/post-quantum-cryptography/workshops-and-timeline. [2] D. Martin, 2015, âReal World Crypto 2015: Password Hashing according to Facebook,â Bristol Cryptography Blog, http://bristolcrypto.blogspot.com/2015/01/password-hashing-according-to-facebook.html [3] D. Martin, 2015, âReal World Crypto 2015: Password Hasing according to Facebook,â Bristol Cryptography Blog, http://bristolcrypto.blogspot.com/2015/01/password-hashing-according-to-facebook.html [4] V. Gheorghiu, M. Mosca, in preparation. [5] M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, 2015, âApplying Groverâs algorithm to AES: quantum resource estimates,â Proceedings of Post-Quantum Cryptography 2016, vol. 9606 of Lecture Notes in Computer Science, pp. 29-43, Springer, 2016; M. Mosca and V. Gheorghiu, 2017, âA Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions,â Global Risk Institute, http://globalriskinstitute.org/publications/resource-estimation- framework-quantum-attacks-cryptographic-functions/ [6] T. HÃ¤ner, M. Roetteler, and K.M. Svore, 2017, âFactoring using 2n+2 qubits with Toffoli based modular multiplication,â Quantum Information and Computation, 18(7and8):673-684.; M. Mosca and V. Gheorghiu, 2017, âA Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions,â Global Risk Institute, http://globalriskinstitute.org/publications/resource-estimation- framework-quantum-attacks-cryptographic-functions/. [7] M. Roetteler, M. Naehrig, K.M. Svore, and K. Lauter, 2017, âQuantum resource estimates for computing elliptic curve discrete logarithms,â Advances in Cryptology ââ ASIACRYPT 2017, Lecture Notes in Computer Science 10625, Springer-Verlag (2017), pp 241-272. [8] M. Mosca and V. Gheorghiu, 2017, âA Resource Estimation Framework for Quantum Attacks Against Cryptographic Functions â - âPart 2 (RSA and ECC),â Global Risk Institute, https://globalriskinstitute.org/publications/resource-estimation-framework-quantum-attacks-cryptographic- functions-part-2-rsa-ecc/. [9] M. Mosca and V. Gheorghiu, 2017, âA Resource Estimation Framework for Quantum Attacks Against Cryptographic Functionsâimprovements,â Global Risk Institute. [10] âPost-Quantum Cryptography,â National Institute of Standards and Technology, last modified May 29, 2018, http://csrc.nist.gov/groups/ST/post-quantum-crypto/. [11] For additional discussion of the process and challenges associated with transitioning between cryptosystems, see National Academies of Sciences, Engineering, and Medicine. 2017. Cryptographic Agility and Interoperability: Proceedings of a Workshop. Washington, DC: The National Academies Press. https://doi.org/10.17226/24636. PREPUBLICATION COPY â SUBJECT TO FURTHER EDITORIAL CORRECTION 4-13