idnits 2.17.1 draft-hoffman-c2pq-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (May 26, 2020) is 1430 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. Hoffman 3 Internet-Draft ICANN 4 Intended status: Informational May 26, 2020 5 Expires: November 27, 2020 7 The Transition from Classical to Post-Quantum Cryptography 8 draft-hoffman-c2pq-07 10 Abstract 12 Quantum computing is the study of computers that use quantum features 13 in calculations. For over 20 years, it has been known that if very 14 large, specialized quantum computers could be built, they could have 15 a devastating effect on asymmetric classical cryptographic algorithms 16 such as RSA and elliptic curve signatures and key exchange, as well 17 as (but in smaller scale) on symmetric cryptographic algorithms such 18 as block ciphers, MACs, and hash functions. There has already been a 19 great deal of study on how to create algorithms that will resist 20 large, specialized quantum computers, but so far, the properties of 21 those algorithms make them onerous to adopt before they are needed. 23 Small quantum computers are being built today, but it is still far 24 from clear when large, specialized quantum computers will be built 25 that can recover private or secret keys in classical algorithms at 26 the key sizes commonly used today. It is important to be able to 27 predict when large, specialized quantum computers usable for 28 cryptanalysis will be possible so that organization can change to 29 post-quantum cryptographic algorithms well before they are needed. 31 This document describes quantum computing, how it might be used to 32 attack classical cryptographic algorithms, and possibly how to 33 predict when large, specialized quantum computers will become 34 feasible. 36 Status of This Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at https://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on November 27, 2020. 53 Copyright Notice 55 Copyright (c) 2020 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (https://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the Simplified BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 71 1.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 3 72 1.2. Executive Summary . . . . . . . . . . . . . . . . . . . . 3 73 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 74 1.4. Where to Read More . . . . . . . . . . . . . . . . . . . 5 75 1.5. Not Covered: Post-Quantum Cryptographic Algorithms . . . 5 76 1.6. Not Covered: Quantum Key Exchange . . . . . . . . . . . . 6 77 2. Brief Introduction to Quantum Computers . . . . . . . . . . . 6 78 2.1. Quantum Computers that Recover Cryptographic Keys . . . . 7 79 3. Physical Designs for Quantum Computers . . . . . . . . . . . 7 80 3.1. Qubits, Error Detection, and Error Correction . . . . . . 8 81 3.2. Promising Physical Designs for Quantum Computers . . . . 8 82 3.3. Challenges for Physical Designs . . . . . . . . . . . . . 8 83 4. Quantum Computers and Public Key Cryptography . . . . . . . . 9 84 4.1. Explanation of Shor's Algorithm . . . . . . . . . . . . . 10 85 4.2. Properties of Large, Specialized Quantum Computers Needed 86 for Recovering RSA Public Keys . . . . . . . . . . . . . 10 87 5. Quantum Computers and Symmetric Key Cryptography . . . . . . 10 88 5.1. Properties of Large, Specialized Quantum Computers Needed 89 for Recovering Symmetric Keys . . . . . . . . . . . . . . 12 90 5.2. Properties of Large, Specialized Quantum Computers for 91 Computing Hash Collisions . . . . . . . . . . . . . . . . 12 92 6. Predicting When Useful Cryptographic Attacks Will Be Feasible 12 93 6.1. Proposal: Public Measurements of Various Quantum 94 Technologies . . . . . . . . . . . . . . . . . . . . . . 13 95 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 96 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 97 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 98 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 99 10.1. Normative References . . . . . . . . . . . . . . . . . . 15 100 10.2. Informative References . . . . . . . . . . . . . . . . . 15 101 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 17 103 1. Introduction 105 Early drafts of this document use "@@@@@" to indicate where the 106 editor particularly want input from reviewers. The editor welcomes 107 all types of review, but the areas marked with "@@@@@" are in the 108 most noticeable need of new material. (The editor particularly 109 appreciates new material that comes with references that can be 110 included in this document as well.) 112 1.1. Disclaimer 114 **** This is still an early version of this draft. **** As such, it 115 has had only some review in the cryptography community. Statements 116 in this document might be wrong; given that the entire document is 117 about cryptography, those wrong statements might have significant 118 security problems associated with them. 120 Readers of this document should not rely on any statements in this 121 version of this draft. As the draft gets more input from the 122 cryptography community over time, this disclaimer will be softened 123 and eventually eliminated. 125 1.2. Executive Summary 127 The development of quantum computers that can recover private or 128 secret keys in classical algorithms at the key sizes commonly used 129 today is at a very early stage. None of the published examples of 130 such quantum computers is useful in recovering keys that are in use 131 today. There is a great amount of interest in this development, and 132 researchers expect large strides in this development in the coming 133 decade. 135 There is active research in standardizing signing and key exchange 136 algorithms that will withstand attacks from large, specialized 137 quantum computers. However, all those algorithms to date have very 138 large keys, very large signatures, or both. Thus, there is a large 139 sustained cost in using those algorithms. Similarly, there is a 140 large cost in being surprised about when quantum computers can cause 141 damage to current cryptographic keys and signatures. 143 Because the world does not know when large, specialized quantum 144 computers that can recover cryptographic keys will be available, 145 organizations should be watching this area so that they have plenty 146 of time to either change to larger key sizes for classical 147 cryptography or to change to post-quantum algorithms. See Section 6 148 for a fuller discussion of determining how to predict when quantum 149 computers that can harm current cryptography might become feasible. 151 1.3. Terminology 153 The term "classical cryptography" is used to indicate the 154 cryptographic algorithms that are in common use today. In 155 particular, signature and key exchange algorithms that are based on 156 the difficulty of factoring numbers into two large prime numbers, or 157 are based on the difficulty of determining the discrete log of a 158 large composite number, are considered classical cryptography. 160 The term "post-quantum cryptography" refers to the invention and 161 study of cryptographic mechanisms in which the security does not rely 162 on computationally hard problems that can be efficiently solved on 163 quantum computers. This excludes systems whose security relies on 164 factoring numbers, or the difficulty of determining the discrete log 165 of one group element with respect to another. 167 Note that these definitions apply to only one aspect of quantum 168 computing as it relates to cryptography. It is expected that quantum 169 computing will also be able to be used against symmetric key 170 cryptography to make it possible to search for a secret symmetric key 171 using far fewer operations than are needed using classical computers 172 (see Section 5 for more detail). However, using longer keys to 173 thwart that possibility is not normally called "post-quantum 174 cryptography". 176 There are many terms that are only used in the field of quantum 177 computing, such as "qubit", "quantum algorithm", and so on. Chapter 178 1 of [NielsenChuang] has good definitions of such terms. 180 Some papers discussing quantum computers and cryptanalysis say that 181 large, specialized quantum computers "break" algorithms in classical 182 cryptography. This paper does not use that terminology because the 183 algorithms' strength will be reduced when large, specialized quantum 184 computers exist, but not to the point where there is an immediate 185 need to change algorithms. 187 The "^" symbol is used to indicate "the power of". The term "log" 188 always means "logarithm base 2". 190 1.4. Where to Read More 192 There are many reasonably accessible articles on Wikipedia, notably 193 the overview article at and the timeline of quantum computing developments 195 at . 197 [NielsenChuang] is a well-regarded college textbook on quantum 198 computers. Prerequisites for understanding the book include linear 199 algebra and some quantum physics; however, even without those, a 200 reader can probably get value from the introductory material in the 201 book. 203 A good overview of the current status of quantum computing in general 204 is [ProgressProspects]. 206 [QCPolicy] describes how the development of quantum computing affects 207 encryption policies. 209 [Turing50Youtube] is a good overview of the near-term and longer-term 210 prospects for designing and building quantum computers; it is a video 211 of a panel discussion by quantum hardware and software experts given 212 at the ACM's Turing 50 lecture. 214 @@@@@ Maybe add more references that might be useful to non-experts. 216 1.5. Not Covered: Post-Quantum Cryptographic Algorithms 218 This document discusses when an organization would want to consider 219 using post-quantum cryptographic algorithms, but definitely does not 220 delve into which of those algorithms would be best to use. Post- 221 quantum cryptography is an active field of research; in fact, it is 222 much more active than the study of when we might want to transition 223 from classical to post-quantum cryptography. 225 Readers interested in post-quantum cryptographic algorithms will have 226 no problem finding many articles proposing such algorithms, comparing 227 the many current proposals, and so on. An excellent starting point 228 is the web site . The Open Quantum Safe (OQS) 229 project is developing and prototyping 230 quantum-resistant cryptography. Another is the article on post- 231 quantum cryptography at Wikipedia: . 234 Various organizations are working on standardizing the algorithms for 235 post-quantum cryptography. For example, the US National Institute of 236 Standards and Technology (commonly just called "NIST") is holding a 237 competition to evaluate post-quantum cryptographic algorithms. 239 NIST's description of that effort is currently at 240 . Until 241 recently, ETSI (the European Telecommunications Standards Institute) 242 had a Quantum-Safe Cryptography (QSC) Industry Specification Group 243 (ISG) that worked on specifying post-quantum algorithms; see 244 for results from this work. 247 1.6. Not Covered: Quantum Key Exchange 249 Other than in this section, this document does not cover "quantum key 250 exchange", also called "quantum cryptography". The field of quantum 251 key exchange uses quantum effects in order to secure communication 252 between users. Quantum key exchange is not related to cryptanalysis. 254 2. Brief Introduction to Quantum Computers 256 A quantum computer is a computer that uses quantum bits (qubits) in 257 quantum circuits to perform calculations. Quantum computers also use 258 classical bits and regular circuits: most calculations in a quantum 259 computer are a mix of classical and quantum bits and circuits. For 260 example, classical bits could be used for error correction or 261 controlling the behavior of physical components of the quantum 262 computer. 264 A basic principle that makes it possible to speed up calculations on 265 qubits in quantum computers is quantum superposition. Informally, 266 similarly to waves in classical physics, arbitrary number of quantum 267 states can be added together and result will be another valid quantum 268 state. That means that, for example, two qubits could be in any 269 quantum superposition of four states, three qubits in quantum 270 superposition of eight states, and so on. Generally n qubits can be 271 in quantum superposition of 2^n states. 273 The main challenge for quantum computing is to create and maintain a 274 significantly large number of superposed qubits while performing 275 quantum computations. Physical components of quantum computers that 276 are non-ideal results in the destruction of qubit state over time; 277 this is the source of errors in quantum computation. See Section 3.1 278 for a description of how to overcome this problem. 280 A good description of different aspects of calculations on quantum 281 computer could be found in [EstimatingPreimage]. 283 A separate question is a measurement of a quantum state. Due to 284 uncertainty of the state, the measurement process is stochastic. 285 That means that in order to get the correct measurement one should 286 run several consequent calculations and corresponding measurement in 287 order to the expected value which is considered as a result of 288 measurement. 290 @@@@@ Discuss measurements and how they have to be done with 291 correlated qubits. 293 2.1. Quantum Computers that Recover Cryptographic Keys 295 Quantum computers are expected to be useful in the future for some 296 problems that take up too many resources on a large classical 297 computer. However, this document only discusses how they might 298 recover cryptographic keys faster than classical computers. In order 299 to recover cryptographic keys, a quantum computer needs to have a 300 quantum circuit specifically designed for the type of key it is 301 attempting to recover. 303 A quantum computer will need to have a circuit with thousands of 304 qubits to be useful to recover the type and size keys that are in 305 common use today. Smaller quantum computers (those with fewer qubits 306 in superposition) are not useful for using Shor's algorithm (as 307 discussed in Section 4.1) at all. That is, no one has devised a way 308 to combine a bunch of smaller quantum computers to perform the same 309 attacks on cryptographic keys via Shor's algorithm as a properly- 310 sized quantum computer. 312 This is why this document uses the term "large, specialized quantum 313 computer" when describing ones that can recover keys: there will 314 certainly be small quantum computers built first, but those computers 315 cannot recover the type and size keys that are in common use today. 316 Further, there are already quantum computers that have many qubits 317 but without the circuits needed to make those qubits useful for 318 recovering cryptographic keys. 320 A straight-forward application of Shor's algorithm may not be the 321 only way for large, specialized quantum computers to attack RSA keys. 322 [LowResource] describes how to combine quantum computers with 323 classical methods for recovering RSA keys at speeds faster than just 324 using the classical methods. 326 3. Physical Designs for Quantum Computers 328 Quantum computers can be built using many different physical 329 technologies. Deciding which physical technologies are best to 330 pursue is an extremely active research topic. A few physical 331 technologies (particularly trapped ions and neutral atoms, super- 332 conduction using Josephson junctions, and nuclear magnetic resonance) 333 are currently getting the most press, but other technologies are also 334 showing promise. 336 One factor that is important to quantum computers that can be used 337 for cryptanalysis is the speed of the operations (transformations) on 338 qubits. Most of the estimates of speeds of these quantum computers 339 assume that qubit operations will take about the same amount of time 340 as operations in circuits that consist of classical gates and 341 classical memory. Current quantum circuits are currently slower than 342 classical circuits, but will certainly become faster as quantum 343 computers are developed in the future. 345 Note that some current quantum computer research uses bits that are 346 not fully entangled, and this will greatly affect their ability to 347 make useful quantum calculations. 349 3.1. Qubits, Error Detection, and Error Correction 351 Researchers building small quantum computers have discovered that 352 calculating the superposition of qubits often has a large rate of 353 error, and that error rate increases rapidly over time. Performing 354 quantum calculations such as those needed to recover cryptographic 355 keys is not feasible with the current state of quantum computers. 357 In the future, actual quantum calculations will be performed on 358 "logical qubits", that is, after the application of error correction 359 codes on physical qubits. Thus, the number of physical qubits will 360 be higher than the number of logical qubits, depending on the 361 parameters of the error correction code, which in turn depends on the 362 parameters of a technology used for a physical implementation of 363 qubits. Currently, it is estimated that it takes hundreds or 364 thousands of physical qubits to make a logical qubit. @@@@@ Need 365 reference for this statement. 367 @@@@@ Lots more material should go here. We will need recent 368 references for how many physical qubits are needed for each corrected 369 qubit. It's OK if this section has lots of references, but hopefully 370 they don't contradict each other. 372 3.2. Promising Physical Designs for Quantum Computers 374 @@@@@ It would be useful to have maybe two paragraphs about each 375 physical design that is being actively pursued. 377 3.3. Challenges for Physical Designs 379 Different designs have different challenges to overcome before the 380 physical technology can be scaled enough to build a useful large, 381 specialized quantum computer. Some of those challenges include the 382 following. (Note that some items on this list apply only to some of 383 the physical technologies.) 384 Temperature: Getting stable operation without extreme cooling is 385 difficult for many of the proposed technologies. The definition 386 of "extreme" is different for different low-temperature 387 technologies. 389 Stabilization: The length of time every qubit in a circuit holds is 390 value 392 Quantum control: Coherence and reproducibility of qubits 394 Error detection and correction: Getting accurate results through 395 simultaneous detection of bit-flip and phase-flip. See 396 Section 3.1 for a longer description of this. 398 Substrate: The material on which the qubit circuits are built. This 399 has a large effect on the stability of the qubits. 401 Particles: The atoms or sub-atomic particles used to make the qubits 403 Scalability: The ability to handle the number of physical qubits 404 needed for the desired the circuit 406 Architecture: Ability to change quantum gates in a circuit 408 4. Quantum Computers and Public Key Cryptography 410 The area of quantum computing that has generated the most interest in 411 the cryptographic community is the ability of quantum computers to 412 find the private keys in encryption and signature algorithms based on 413 discrete logarithms using exponentially fewer operations than 414 classical computers would need to use. 416 As described in [RFC3766], it is widely believed that factoring large 417 numbers and finding discrete logs using classical computers increases 418 with the exponential size of the key. [RFC3766] describes in detail 419 how classical computers can be used to determine keys; even though 420 that RFC is over a decade old, no significant changes have been made 421 to the process of classical attacks on RSA and Diffie-Hellman. @@@@@ 422 CFRG: is that true? Does RFC 3766 need to be updated? 424 Shor's algorithm shows that these problems can be solved on quantum 425 computers in polynomial time, meaning that the speed of finding the 426 keys is a polynomial function (with reasonable-sized coefficients) 427 based on the size of the keys, which would require significantly 428 fewer steps than a classical computer. The definitive paper on 429 Shor's algorithm is [Shor97]. 431 4.1. Explanation of Shor's Algorithm 433 @@@@@ Pointers to understandable articles would be good here. 435 @@@@@ Describe period-finding and why it applies to finding prime 436 factors and discrete logs. 438 @@@@@ Give the steps for applying Shor's algorithm to 2048-bit RSA. 439 Describe how many rounds of the quantum subroutine would likely be 440 needed. Describe how many rounds of the classical loop would likely 441 be needed. 443 [ResourceElliptic] gives concrete estimates of the resources needed 444 to build a quantum computer to compute elliptic curve discrete 445 logarithms. It shows that for the common P-256 elliptic curve, 2330 446 logical qubits and over 10^11 Toffoli gates. 448 [PrimeFactAnneal] describes a method of converting the integer 449 factorization problem to one that can be executed on an adiabatic 450 quantum computer. Adiabatic quantum computers are already available 451 today, such as those from D-Wave Systems. Note that this method is 452 not a way to run Shor's algorithm on an adiabatic quantum computer. 454 4.2. Properties of Large, Specialized Quantum Computers Needed for 455 Recovering RSA Public Keys 457 Researchers have built small quantum computers that implement Shor's 458 algorithm, factoring numbers with four or five bits. These are used 459 to show that Shor's algorithm is possible to realize in actual 460 hardware. (Note, however, that [PretendingFactor] indicates that 461 these experiments may have taken shortcuts that prevent them from 462 indicating real Shor designs.) 464 @@@@@ References are needed here. Did they implement all of Shor's 465 algorithm, including the looping logic in the classical part and the 466 looping logic in the quantum part? 468 According to [GidneyEkera], a quantum computer that can determine the 469 private keys for 2048-bit RSA would require 20 million correlated 470 qubits. The paper estimates a similar order of size for a quantum 471 computer that could determine the private key for 256-bit elliptic 472 curve algorithms. 474 5. Quantum Computers and Symmetric Key Cryptography 476 Section 4 is about Shor's algorithm and compromises to public key 477 cryptography. There is a second quantum computing algorithm, 478 Grover's algorithm, that is often mentioned at the same time as 479 Shor's algorithm. With respect to cryptanalysis, however, Grover's 480 algorithm applies to tasks of finding a preimage, including tasks of 481 finding a secret key of a symmetric algorithm such as AES if there is 482 knowledge of plaintext-ciphertext pairs. The definitive paper on 483 Grover's algorithm is by Grover: [Grover96]. Grover later wrote a 484 more accessible paper about the algorithm in [QuantumSearch]. 486 Grover's algorithm gives a way to search for keys to symmetric 487 algorithms in the square root of the time that a normal exhaustive 488 search would take. Thus, a large, specialized quantum computer that 489 implements Grover's algorithm could find a secret AES-128 key in 490 about 2^64 steps instead of the 2^128 steps that would be required 491 for a classical computer. 493 When it appears that it is feasible to build a large, specialized 494 quantum computer that can defeat a particular symmetric algorithm at 495 a particular key size, the proper response would be to use keys with 496 twice as many bits. That is, if one is using the AES-128 algorithm 497 and there is a concern that an adversary might be able to build a 498 large, specialized quantum computer that is designed to attack 499 AES-128 keys, move to an algorithm that has keys twice as long as 500 AES-128, namely AES-256 (the block size used is not significant 501 here). 503 By some estimates, large specialized quantum computers that implement 504 Grover's algorithm might be built before ones that implement Shor's 505 algorithm are. There are two primary reasons for this: 507 o Grover's algorithm is likely to be useful in areas other than 508 cryptography. For example, a large, specialized quantum computer 509 that implements Grover's algorithm might help create medicines by 510 speeding up complex problems that involve how proteins fold. @@@@@ 511 Add more likely examples and references here. 513 o A large, specialized quantum computer that can recover AES-128 514 keys will likely be much smaller (and thus easier to build) than 515 one that implements Shor's algorithm for 256-bit elliptic curves 516 or 2048-bit RSA/DSA keys. 518 There are arguments against the likelihood of building computers 519 using Grover's algorithm to break AES-128. As described in 520 [FindCollisions]: 522 o Breaking AES-128 with Grover's method could be infeasible due to 523 inherent inefficiencies in the algorithm. For example, the 524 overhead of the quantum operations in the algorithm might be huge 525 when compared to non-quantum operations. 527 o Grover's algorithm has not been parallelized in a quantum 528 computer, so the 2^64 steps must be done serially. Unless the 529 speed of quantum computations become as fast as current classical 530 computers, this will make doing all the calculations needed to 531 break an AES-128 key take so long as to be infeasible. 533 5.1. Properties of Large, Specialized Quantum Computers Needed for 534 Recovering Symmetric Keys 536 [ApplyingGrover] estimates that a quantum computer that can determine 537 the secret keys for AES-128 would require 2953 correlated qubits and 538 2.74 * 2^86 gates. 540 [GoverSDES] shows how to use Grover's algorithm to search for keys in 541 SDES, a simplifed version of the DES encryption algorithm. 543 5.2. Properties of Large, Specialized Quantum Computers for Computing 544 Hash Collisions 546 @@@@@ More goes here. Also, discuss how Grover's algorithm does not 547 appear to be useful for computing preimages (or say how it might be 548 used). 550 6. Predicting When Useful Cryptographic Attacks Will Be Feasible 552 If quantum computers that perform useful cryptographic attacks can be 553 built in the future, many organizations will want to start using 554 post-quantum algorithms well before those computers can be built. 555 However, given how few implementations of such quantum computers 556 exist (even for tiny keys), it is impossible to predict with any 557 accuracy when quantum computers that perform useful cryptographic 558 attacks will be feasible. 560 The term "useful" above is relative to the value of the material 561 being protected by the cryptographic algorithm to the attacker. For 562 example, if the quantum computer attacking a particular key costs 563 US$100 billion to build, costs US$1 billion a year to run, and can 564 extract only one key a year, it is possibly useful to some 565 governments, but probably not useful for attacking the TLS key used 566 to protect a small mail server. On the other hand, if later a 567 similar computer costs US$1 billion to build, costs US$10 million a 568 year to run, and can extract ten keys a year, many more keys become 569 vulnerable. 571 [BeReady] gives a simple way to approach the calculation of when one 572 needs to deploy post-quantum algorithms. In short, if the sum of how 573 long you need your keys to be secure plus how long it takes to deploy 574 new algorithms is longer than the length of time it will take for an 575 attacker to create a large, specialized quantum computer and use it 576 against your keys, then you waited too long. 578 To date, few people have done systematic research that would give 579 estimates for when useful quantum-based cryptographic attacks might 580 be feasible, and at what cost. Without such research, it is easy to 581 make wild guesses but those are not of much value to people having to 582 decide when to start using post-quantum cryptography. 584 For example, in [NIST8105], NIST says "researchers working on 585 building a quantum computer have estimated that it is likely that a 586 quantum computer capable of recovering 2000-bit RSA in a matter of 587 hours could be built by 2030 for a budget of about a billion 588 dollars". However, the referenced link is to a YouTube video 589 [MariantoniYoutube] where the researcher, Matteo Mariantoni, says 590 "maybe you should not quote me on that". [NIST8105] gives no other 591 references for predictions on cost and availability of useful 592 cryptographic attacks with quantum computers. 594 6.1. Proposal: Public Measurements of Various Quantum Technologies 596 In order to get a rough idea of when useful cryptographic attacks 597 with quantum computers may be feasible, researchers creating such 598 computers can demonstrate them when they can recover keys an eighth 599 the size of those in common use. That is, given that 2048-bit RSA, 600 256-bit elliptic curve, and AES-128 are common today, when a research 601 team has a computer than can recover 256-bit RSA, 32-bit elliptic 602 curve, or AES-128 where only 16 bits are unknown, they should 603 demonstrate it. 605 Such a demonstration could easily be made fair with trusted 606 representatives from the cryptographic community using verifiable 607 means to pick the keys to recover, and verifying the time that it 608 takes to recover each key. It might be interesting to run the same 609 tests in classical computers at the same time to give perspective. 611 These demonstrations will have many benefits to those who have to 612 decide when post-quantum algorithms should be deployed in various 613 environments. 615 o Demonstrations will likely use designs that are considered most 616 efficient. This in turn will cause greater focus research on 617 choosing good design candidates. 619 o The results of the demonstrations will help focus on issues 620 important to cryptanalysis, namely the cost of building the 621 systems and the speed of breaking a single key. 623 o Competing demonstrations will reveal where different research 624 teams have made different optimizations from well-known designs. 626 o Public demonstrations could expose designs that work only in 627 limited cases that are uncommon in normal cryptographic practice. 628 (For example, [PretendingFactor] claims that all current 629 factorization experiments have taken advantage of using a 630 classical computer that already knows the answer to design the 631 quantum circuits.) 633 Note that this proposal would only give an idea of how public 634 progress is being made on quantum computers. Well-funded military 635 agencies (and possibly even criminal enterprises) could be way ahead 636 of the publicly-visible computers. No one should rely on just the 637 public measurements when deciding how safe their keys are against 638 quantum computers. 640 7. IANA Considerations 642 None, and thus this section can be removed at final publication. 644 8. Security Considerations 646 This entire document is about cryptography, and thus about security. 648 See Section 1.1 for an important disclaimer about this document and 649 security. 651 This document is meant to help the reader predict when to transition 652 from using classical cryptographic algorithms to post-quantum 653 algorithms. That decision is ultimately up to the reader, and must 654 be made not only based on predictions of how quantum computing is 655 progressing but also the value of every key that the user handles. 656 For example, a financial institution using TLS to protect its 657 customers' transactions will probably consider its keys more valuable 658 than a small online store, and will thus be likely to begin the 659 transition earlier. 661 9. Acknowledgements 663 The list here is meant to acknowledge input to this document. The 664 people listed here do not necessarily agree with ideas presented. 666 Many sections of text were contributed by Grigory Marshalko and 667 Stanislav Smyshlyaev. 669 Some of the ideas in this document come from Denis Butin, Philip 670 Lafrance, Hilarie Orman, and Tomofumi Okubo. 672 10. References 674 10.1. Normative References 676 [Grover96] 677 Grover, L., "A fast quantum mechanical algorithm for 678 database search", 1996, 679 . 681 [Shor97] Shor, P., "Polynomial-Time Algorithms for Prime 682 Factorization and Discrete Logarithms on a Quantum 683 Computer", 1997, 684 . 686 10.2. Informative References 688 [ApplyingGrover] 689 Grassl, M., Langenberg, B., Roetteler, M., and R. 690 Steinwandt, "Applying Grover's algorithm to AES: quantum 691 resource estimates", 2015, 692 . 694 [BeReady] Mosca, M., "Cybersecurity in an era with quantum 695 computers: will we be ready?", 2015, 696 . 698 [EstimatingPreimage] 699 Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, 700 A., and J. Schanck, "Estimating the cost of generic 701 quantum pre-image attacks on SHA-2 and SHA-3", 2016, 702 . 704 [FindCollisions] 705 Bernstein, D., "Quantum algorithms to find collisions", 706 2017, . 708 [GidneyEkera] 709 Gidney, C. and M. Ekera, "How to factor 2048 bit RSA 710 integers in 8 hours using 20 million noisy qubits", 2019, 711 . 713 [GoverSDES] 714 Denisenko, D. and M. Nikitenkova, "Application of Grover's 715 Quantum Algorithm for SDES Key Searching", 2018. 717 [LowResource] 718 Bernstein, D., Fiassse, J., and M. Mosca, "A low-resource 719 quantum factoring algorithm", 2017, 720 . 722 [MariantoniYoutube] 723 Mariantoni, M., "Building a Superconducting Quantum 724 Computer", 2014, 725 . 727 [NielsenChuang] 728 Nielsen, M. and I. Chuang, "Quantum Computation and 729 Quantum Information, 10th Anniversary Edition", ISBN 730 97801-107-00217-3 , 2010. 732 [NIST8105] 733 Chen, L. and et. al, "Report on Post-Quantum 734 Cryptography", 2016, 735 . 738 [PretendingFactor] 739 Smolin, J., Vargo, A., and J. Smolin, "Pretending to 740 factor large numbers on a quantum computer", 2013, 741 . 743 [PrimeFactAnneal] 744 Jiang, S., Britt, K., McCaskey, A., Humble, T., and S. 745 Kais, "Quantum Annealing for Prime Factorization", 2018, 746 . 748 [ProgressProspects] 749 The National Acadamies Sciences Engineering Medicine, 750 "Quantum Computing: Progress and Prospects (2019)", 2019, 751 . 754 [QCPolicy] 755 Princeton University Center for Information Technology 756 Policy, "Implications of Quantum Computing for Encryption 757 Policy", 2019, . 761 [QuantumSearch] 762 Grover, L., "From Schrodinger's Equation to the Quantum 763 Search Algorithm", 2001, 764 . 766 [ResourceElliptic] 767 Roetteler, M., Naehrig, M., Svore, K., and K. Lauter, 768 "Quantum Resource Estimates for Computing Elliptic Curve 769 Discrete Logarithms", 2017, 770 . 772 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For 773 Public Keys Used For Exchanging Symmetric Keys", BCP 86, 774 RFC 3766, DOI 10.17487/RFC3766, April 2004, 775 . 777 [Turing50Youtube] 778 Vazirani, U., Aharonov, D., Gambetta, J., Martinis, J., 779 and A. Yao, "Quantum Computing: Far Away? Around the 780 Corner?", 2017, 781 . 783 Author's Address 785 Paul Hoffman 786 ICANN 788 Email: paul.hoffman@icann.org