idnits 2.17.1
draft-hoffman-c2pq-04.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 (August 13, 2018) is 2076 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 August 13, 2018
5 Expires: February 14, 2019
7 The Transition from Classical to Post-Quantum Cryptography
8 draft-hoffman-c2pq-04
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 February 14, 2019.
53 Copyright Notice
55 Copyright (c) 2018 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. Not Covered: Post-Quantum Cryptographic Algorithms . . . 5
75 1.5. Not Covered: Quantum Cryptography . . . . . . . . . . . . 5
76 1.6. Where to Read More . . . . . . . . . . . . . . . . . . . 5
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 . . . . . . . . . . . . . . . . . . . . . . . . 16
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 an early version of this draft. **** As such, it has had
115 little in-depth review in the cryptography community. Statements in
116 this document might be wrong; given that the entire document is about
117 cryptography, those wrong statements might have significant security
118 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. Not Covered: Post-Quantum Cryptographic Algorithms
192 This document discusses when an organization would want to consider
193 using post-quantum cryptographic algorithms, but definitely does not
194 delve into which of those algorithms would be best to use. Post-
195 quantum cryptography is an active field of research; in fact, it is
196 much more active than the study of when we might want to transition
197 from classical to post-quantum cryptography.
199 Readers interested in post-quantum cryptographic algorithms will have
200 no problem finding many articles proposing such algorithms, comparing
201 the many current proposals, and so on. An excellent starting point
202 is the web site . The Open Quantum Safe (OQS)
203 project is developing and prototyping
204 quantum-resistant cryptography. Another is the article on post-
205 quantum cryptography at Wikipedia: .
208 Various organizations are working on standardizing the algorithms for
209 post-quantum cryptography. For example, the US National Institute of
210 Standards and Technology (commonly just called "NIST") is holding a
211 competition to evaluate post-quantum cryptographic algorithms.
212 NIST's description of that effort is currently at
213 . Until
214 recently, ETSI (the European Telecommunications Standards Institute)
215 had a Quantum-Safe Cryptography (QSC) Industry Specification Group
216 (ISG) that worked on specifying post-quantum algorithms; see
217 for results from this work.
220 1.5. Not Covered: Quantum Cryptography
222 Other than in this section, this document does not cover "quantum
223 cryptography". The field of quantum cryptography uses quantum
224 effects in order to secure communication between users. Quantum
225 cryptography is not related to cryptanalysis. The best known and
226 extensively studied example of quantum cryptography is a quantum key
227 exchange, where users can share a secret key while preventing an
228 eavesdropper from obtaining the key.
230 1.6. Where to Read More
232 There are many reasonably accessible articles on Wikipedia, notably
233 the overview article at and the timeline of quantum computing developments
235 at .
237 [NielsenChuang] is a well-regarded college textbook on quantum
238 computers. Prerequisites for understanding the book include linear
239 algebra and some quantum physics; however, even without those, a
240 reader can probably get value from the introductory material in the
241 book.
243 [Turing50Youtube] is a good overview of the near-term and longer-term
244 prospects for designing and building quantum computers; it is a video
245 of a panel discussion by quantum hardware and software experts given
246 at the ACM's Turing 50 lecture.
248 @@@@@ Maybe add more references that might be useful to non-experts.
250 2. Brief Introduction to Quantum Computers
252 A quantum computer is a computer that uses quantum bits (qubits) in
253 quantum circuits to perform calculations. Quantum computers also use
254 classical bits and regular circuits: most calculations in a quantum
255 computer are a mix of classical and quantum bits and circuits. For
256 example, classical bits could be used for error correction or
257 controlling the behavior of physical components of the quantum
258 computer.
260 A basic principle that makes it possible to speed up calculations on
261 qubits in quantum computers is quantum superposition. Informally,
262 similarly to waves in classical physics, arbitrary number of quantum
263 states can be added together and result will be another valid quantum
264 state. That means that, for example, two qubits could be in any
265 quantum superposition of four states, three qubits in quantum
266 superposition of eight states, and so on. Generally n qubits can be
267 in quantum superposition of 2^n states.
269 The main challenge for quantum computing is to create and maintain a
270 significantly large number of superposed qubits while performing
271 quantum computations. Physical components of quantum computers that
272 are non-ideal results in the destruction of qubit state over time;
273 this is the source of errors in quantum computation. See Section 3.1
274 for a description of how to overcome this problem.
276 A good description of different aspects of calculations on quantum
277 computer could be found in [EstimatingPreimage].
279 A separate question is a measurement of a quantum state. Due to
280 uncertainty of the state, the measurement process is stochastic.
281 That means that in order to get the correct measurement one should
282 run several consequent calculations and corresponding measurement in
283 order to the expected value which is considered as a result of
284 measurement.
286 @@@@@ Discuss measurements and how they have to be done with
287 correlated qubits.
289 2.1. Quantum Computers that Recover Cryptographic Keys
291 Quantum computers are expected to be useful in the future for some
292 problems that take up too many resources on a large classical
293 computer. However, this document only discusses how they might
294 recover cryptographic keys faster than classical computers. In order
295 to recover cryptographic keys, a quantum computer needs to have a
296 quantum circuit specifically designed for the type of key it is
297 attempting to recover.
299 A quantum computer will need to have a circuit with thousands of
300 qubits to be useful to recover the type and size keys that are in
301 common use today. Smaller quantum computers (those with fewer qubits
302 in superposition) are not useful for using Shor's algorithm (as
303 discussed in Section 4.1) at all. That is, no one has devised a way
304 to combine a bunch of smaller quantum computers to perform the same
305 attacks on cryptographic keys via Shor's algorithm as a properly-
306 sized quantum computer.
308 This is why this document uses the term "large, specialized quantum
309 computer" when describing ones that can recover keys: there will
310 certainly be small quantum computers built first, but those computers
311 cannot recover the type and size keys that are in common use today.
312 Further, there are already quantum computers that have many qubits
313 but without the circuits needed to make those qubits useful for
314 recovering cryptographic keys.
316 A straight-forward application of Shor's algorithm may not be the
317 only way for large, specialized quantum computers to attack RSA keys.
318 [LowResource] describes how to combine quantum computers with
319 classical methods for recovering RSA keys at speeds faster than just
320 using the classical methods.
322 3. Physical Designs for Quantum Computers
324 Quantum computers can be built using many different physical
325 technologies. Deciding which physical technologies are best to
326 pursue is an extremely active research topic. A few physical
327 technologies (particularly trapped ions and neutral atoms, super-
328 conduction using Josephson junctions, and nuclear magnetic resonance)
329 are currently getting the most press, but other technologies are also
330 showing promise.
332 One factor that is important to quantum computers that can be used
333 for cryptanalysis is the speed of the operations (transformations) on
334 qubits. Most of the estimates of speeds of these quantum computers
335 assume that qubit operations will take about the same amount of time
336 as operations in circuits that consist of classical gates and
337 classical memory. Current quantum circuits are currently slower than
338 classical circuits, but will certainly become faster as quantum
339 computers are developed in the future.
341 Note that some current quantum computer research uses bits that are
342 not fully entangled, and this will greatly affect their ability to
343 make useful quantum calculations.
345 3.1. Qubits, Error Detection, and Error Correction
347 Researchers building small quantum computers have discovered that
348 calculating the superposition of qubits often has a large rate of
349 error, and that error rate increases rapidly over time. Performing
350 quantum calculations such as those needed to recover cryptographic
351 keys is not feasible with the current state of quantum computers.
353 In the future, actual quantum calculations will be performed on
354 "logical qubits", that is, after the application of error correction
355 codes on physical qubits. Thus, the number of physical qubits will
356 be higher than the number of logical qubits, depending on the
357 parameters of the error correction code, which in turn depends on the
358 parameters of a technology used for a physical implementation of
359 qubits. Currently, it is estimated that it takes hundreds or
360 thousands of physical qubits to make a logical qubit. @@@@@ Need
361 reference for this statement.
363 @@@@@ Lots more material should go here. We will need recent
364 references for how many physical qubits are needed for each corrected
365 qubit. It's OK if this section has lots of references, but hopefully
366 they don't contradict each other.
368 3.2. Promising Physical Designs for Quantum Computers
370 @@@@@ It would be useful to have maybe two paragraphs about each
371 physical design that is being actively pursued.
373 3.3. Challenges for Physical Designs
375 Different designs have different challenges to overcome before the
376 physical technology can be scaled enough to build a useful large,
377 specialized quantum computer. Some of those challenges include the
378 following. (Note that some items on this list apply only to some of
379 the physical technologies.)
380 Temperature: Getting stable operation without extreme cooling is
381 difficult for many of the proposed technologies. The definition
382 of "extreme" is different for different low-temperature
383 technologies.
385 Stabilization: The length of time every qubit in a circuit holds is
386 value
388 Quantum control: Coherence and reproducibility of qubits
390 Error detection and correction: Getting accurate results through
391 simultaneous detection of bit-flip and phase-flip. See
392 Section 3.1 for a longer description of this.
394 Substrate: The material on which the qubit circuits are built. This
395 has a large effect on the stability of the qubits.
397 Particles: The atoms or sub-atomic particles used to make the qubits
399 Scalability: The ability to handle the number of physical qubits
400 needed for the desired the circuit
402 Architecture: Ability to change quantum gates in a circuit
404 4. Quantum Computers and Public Key Cryptography
406 The area of quantum computing that has generated the most interest in
407 the cryptographic community is the ability of quantum computers to
408 find the private keys in encryption and signature algorithms based on
409 discrete logarithms using exponentially fewer operations than
410 classical computers would need to use.
412 As described in [RFC3766], it is widely believed that factoring large
413 numbers and finding discrete logs using classical computers increases
414 with the exponential size of the key. [RFC3766] describes in detail
415 how classical computers can be used to determine keys; even though
416 that RFC is over a decade old, no significant changes have been made
417 to the process of classical attacks on RSA and Diffie-Hellman. @@@@@
418 CFRG: is that true? Does RFC 3766 need to be updated?
420 Shor's algorithm shows that these problems can be solved on quantum
421 computers in polynomial time, meaning that the speed of finding the
422 keys is a polynomial function (with reasonable-sized coefficients)
423 based on the size of the keys, which would require significantly
424 fewer steps than a classical computer. The definitive paper on
425 Shor's algorithm is [Shor97].
427 4.1. Explanation of Shor's Algorithm
429 @@@@@ Pointers to understandable articles would be good here.
431 @@@@@ Describe period-finding and why it applies to finding prime
432 factors and discrete logs.
434 @@@@@ Give the steps for applying Shor's algorithm to 2048-bit RSA.
435 Describe how many rounds of the quantum subroutine would likely be
436 needed. Describe how many rounds of the classical loop would likely
437 be needed.
439 [ResourceElliptic] gives concrete estimates of the resources needed
440 to build a quantum computer to compute elliptic curve discrete
441 logarithms. It shows that for the common P-256 elliptic curve, 2330
442 logical qubits and over 10^11 Toffoli gates.
444 4.2. Properties of Large, Specialized Quantum Computers Needed for
445 Recovering RSA Public Keys
447 Researchers have built small quantum computers that implement Shor's
448 algorithm, factoring numbers with four or five bits. These are used
449 to show that Shor's algorithm is possible to realize in actual
450 hardware. (Note, however, that [PretendingFactor] indicates that
451 these experiments may have taken shortcuts that prevent them from
452 indicating real Shor designs.)
454 @@@@@ References are needed here. Did they implement all of Shor's
455 algorithm, including the looping logic in the classical part and the
456 looping logic in the quantum part?
458 @@@@@ Numbers and explanation is needed below:
460 A quantum computer that can determine the private keys for 2048-bit
461 RSA would require SOME NUMBER GOES HERE correlated qubits and SOME
462 NUMBER GOES HERE circuit elements. A quantum computer that can
463 determine the private keys for 256-bt elliptic curves would require
464 SOME NUMBER GOES HERE correlated qubits and SOME NUMBER GOES HERE
465 circuit elements.
467 5. Quantum Computers and Symmetric Key Cryptography
469 Section 4 is about Shor's algorithm and compromises to public key
470 cryptography. There is a second quantum computing algorithm,
471 Grover's algorithm, that is often mentioned at the same time as
472 Shor's algorithm. With respect to cryptanalysis, however, Grover's
473 algorithm applies to tasks of finding a preimage, including tasks of
474 finding a secret key of a symmetric algorithm such as AES if there is
475 knowledge of plaintext-ciphertext pairs. The definitive paper on
476 Grover's algorithm is by Grover: [Grover96]. Grover later wrote a
477 more accessible paper about the algorithm in [QuantumSearch].
479 Grover's algorithm gives a way to search for keys to symmetric
480 algorithms in the square root of the time that a normal exhaustive
481 search would take. Thus, a large, specialized quantum computer that
482 implements Grover's algorithm could find a secret AES-128 key in
483 about 2^64 steps instead of the 2^128 steps that would be required
484 for a classical computer.
486 When it appears that it is feasible to build a large, specialized
487 quantum computer that can defeat a particular symmetric algorithm at
488 a particular key size, the proper response would be to use keys with
489 twice as many bits. That is, if one is using the AES-128 algorithm
490 and there is a concern that an adversary might be able to build a
491 large, specialized quantum computer that is designed to attack
492 AES-128 keys, move to an algorithm that has keys twice as long as
493 AES-128, namely AES-256 (the block size used is not significant
494 here).
496 It is currently expected that large, specialized quantum computers
497 that implement Grover's algorithm may be built before ones that
498 implement Shor's algorithm are. There are two primary reasons for
499 this:
501 o Grover's algorithm is likely to be useful in areas other than
502 cryptography. For example, a large, specialized quantum computer
503 that implements Grover's algorithm might help create medicines by
504 speeding up complex problems that involve how proteins fold. @@@@@
505 Add more likely examples and references here.
507 o A large, specialized quantum computer that can recover AES-128
508 keys will likely be much smaller (and thus easier to build) than
509 one that implements Shor's algorithm for 256-bit elliptic curves
510 or 2048-bit RSA/DSA keys.
512 There are arguments against the likelihood of building computers
513 using Grover's algorithm to break AES-128. As described in
514 [FindCollisions]:
516 o Breaking AES-128 with Grover's method could be infeasible due to
517 inherent inefficiencies in the algorithm. For example, the
518 overhead of the quantum operations in the algorithm might be huge
519 when compared to non-quantum operations.
521 o Grover's algorithm has not been parallelized in a quantum
522 computer, so the 2^64 steps must be done serially. Unless the
523 speed of quantum computations become as fast as current classical
524 computers, this will make doing all the calculations needed to
525 break an AES-128 key take so long as to be infeasible.
527 5.1. Properties of Large, Specialized Quantum Computers Needed for
528 Recovering Symmetric Keys
530 [ApplyingGrover] estimates that a quantum computer that can determine
531 the secret keys for AES-128 would require 2953 correlated qubits and
532 2.74 * 2^86 gates.
534 5.2. Properties of Large, Specialized Quantum Computers for Computing
535 Hash Collisions
537 @@@@@ More goes here. Also, discuss how Grover's algorithm does not
538 appear to be useful for computing preimages (or say how it might be
539 used).
541 6. Predicting When Useful Cryptographic Attacks Will Be Feasible
543 If quantum computers that perform useful cryptographic attacks can be
544 built in the future, many organizations will want to start using
545 post-quantum algorithms well before those computers can be built.
546 However, given how few implementations of such quantum computers
547 exist (even for tiny keys), it is impossible to predict with any
548 accuracy when quantum computers that perform useful cryptographic
549 attacks will be feasible.
551 The term "useful" above is relative to the value of the material
552 being protected by the cryptographic algorithm to the attacker. For
553 example, if the quantum computer attacking a particular key costs
554 US$100 billion to build, costs US$1 billion a year to run, and can
555 extract only one key a year, it is possibly useful to some
556 governments, but probably not useful for attacking the TLS key used
557 to protect a small mail server. On the other hand, if later a
558 similar computer costs US$1 billion to build, costs US$10 million a
559 year to run, and can extract ten keys a year, many more keys become
560 vulnerable.
562 [BeReady] gives a simple way to approach the calculation of when one
563 needs to deploy post-quantum algorithms. In short, if the sum of how
564 long you need your keys to be secure plus how long it takes to deploy
565 new algorithms is longer than the length of time it will take for an
566 attacker to create a large, specialized quantum computer and use it
567 against your keys, then you waited too long.
569 To date, few people have done systematic research that would give
570 estimates for when useful quantum-based cryptographic attacks might
571 be feasible, and at what cost. Without such research, it is easy to
572 make wild guesses but those are not of much value to people having to
573 decide when to start using post-quantum cryptography.
575 For example, in [NIST8105], NIST says "researchers working on
576 building a quantum computer have estimated that it is likely that a
577 quantum computer capable of recovering 2000-bit RSA in a matter of
578 hours could be built by 2030 for a budget of about a billion
579 dollars". However, the referenced link is to a YouTube video
580 [MariantoniYoutube] where the researcher, Matteo Mariantoni, says
581 "maybe you should not quote me on that". [NIST8105] gives no other
582 references for predictions on cost and availability of useful
583 cryptographic attacks with quantum computers.
585 6.1. Proposal: Public Measurements of Various Quantum Technologies
587 In order to get a rough idea of when useful cryptographic attacks
588 with quantum computers may be feasible, researchers creating such
589 computers can demonstrate them when they can recover keys an eighth
590 the size of those in common use. That is, given that 2048-bit RSA,
591 256-bit elliptic curve, and AES-128 are common today, when a research
592 team has a computer than can recover 256-bit RSA, 32-bit elliptic
593 curve, or AES-128 where only 16 bits are unknown, they should
594 demonstrate it.
596 Such a demonstration could easily be made fair with trusted
597 representatives from the cryptographic community using verifiable
598 means to pick the keys to recover, and verifying the time that it
599 takes to recover each key. It might be interesting to run the same
600 tests in classical computers at the same time to give perspective.
602 These demonstrations will have many benefits to those who have to
603 decide when post-quantum algorithms should be deployed in various
604 environments.
606 o Demonstrations will likely use designs that are considered most
607 efficient. This in turn will cause greater focus research on
608 choosing good design candidates.
610 o The results of the demonstrations will help focus on issues
611 important to cryptanalysis, namely the cost of building the
612 systems and the speed of breaking a single key.
614 o Competing demonstrations will reveal where different research
615 teams have made different optimizations from well-known designs.
617 o Public demonstrations could expose designs that work only in
618 limited cases that are uncommon in normal cryptographic practice.
620 (For example, [PretendingFactor] claims that all current
621 factorization experiments have taken advantage of using a
622 classical computer that already knows the answer to design the
623 quantum circuits.)
625 Note that this proposal would only give an idea of how public
626 progress is being made on quantum computers. Well-funded military
627 agencies (and possibly even criminal enterprises) could be way ahead
628 of the publicly-visible computers. No one should rely on just the
629 public measurements when deciding how safe their keys are against
630 quantum computers.
632 7. IANA Considerations
634 None, and thus this section can be removed at final publication.
636 8. Security Considerations
638 This entire document is about cryptography, and thus about security.
640 See Section 1.1 for an important disclaimer about this document and
641 security.
643 This document is meant to help the reader predict when to transition
644 from using classical cryptographic algorithms to post-quantum
645 algorithms. That decision is ultimately up to the reader, and must
646 be made not only based on predictions of how quantum computing is
647 progressing but also the value of every key that the user handles.
648 For example, a financial institution using TLS to protect its
649 customers' transactions will probably consider its keys more valuable
650 than a small online store, and will thus be likely to begin the
651 transition earlier.
653 9. Acknowledgements
655 The list here is meant to acknowledge input to this document. The
656 people listed here do not necessarily agree with ideas presented.
658 Many sections of text were contributed by Grigory Marshalko and
659 Stanislav Smyshlyaev.
661 Some of the ideas in this document come from Denis Butin, Philip
662 Lafrance, Hilarie Orman, and Tomofumi Okubo.
664 10. References
666 10.1. Normative References
668 [Grover96]
669 Grover, L., "A fast quantum mechanical algorithm for
670 database search", 1996,
671 .
673 [Shor97] Shor, P., "Polynomial-Time Algorithms for Prime
674 Factorization and Discrete Logarithms on a Quantum
675 Computer", 1997,
676 .
678 10.2. Informative References
680 [ApplyingGrover]
681 Grassl, M., Langenberg, B., Roetteler, M., and R.
682 Steinwandt, "Applying Grover's algorithm to AES: quantum
683 resource estimates", 2015,
684 .
686 [BeReady] Mosca, M., "Cybersecurity in an era with quantum
687 computers: will we be ready?", 2015,
688 .
690 [EstimatingPreimage]
691 Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent,
692 A., and J. Schanck, "Estimating the cost of generic
693 quantum pre-image attacks on SHA-2 and SHA-3", 2016,
694 .
696 [FindCollisions]
697 Bernstein, D., "Quantum algorithms to find collisions",
698 2017, .
700 [LowResource]
701 Bernstein, D., Fiassse, J., and M. Mosca, "A low-resource
702 quantum factoring algorithm", 2017,
703 .
705 [MariantoniYoutube]
706 Mariantoni, M., "Building a Superconducting Quantum
707 Computer", 2014,
708 .
710 [NielsenChuang]
711 Nielsen, M. and I. Chuang, "Quantum Computation and
712 Quantum Information, 10th Anniversary Edition", ISBN
713 97801-107-00217-3 , 2010.
715 [NIST8105]
716 Chen, L. and et. al, "Report on Post-Quantum
717 Cryptography", 2016,
718 .
721 [PretendingFactor]
722 Smolin, J., Vargo, A., and J. Smolin, "Pretending to
723 factor large numbers on a quantum computer", 2013,
724 .
726 [QuantumSearch]
727 Grover, L., "From Schrodinger's Equation to the Quantum
728 Search Algorithm", 2001,
729 .
731 [ResourceElliptic]
732 Roetteler, M., Naehrig, M., Svore, K., and K. Lauter,
733 "Quantum Resource Estimates for Computing Elliptic Curve
734 Discrete Logarithms", 2017,
735 .
737 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For
738 Public Keys Used For Exchanging Symmetric Keys", BCP 86,
739 RFC 3766, DOI 10.17487/RFC3766, April 2004,
740 .
742 [Turing50Youtube]
743 Vazirani, U., Aharonov, D., Gambetta, J., Martinis, J.,
744 and A. Yao, "Quantum Computing: Far Away? Around the
745 Corner?", 2017,
746 .
748 Author's Address
750 Paul Hoffman
751 ICANN
753 Email: paul.hoffman@icann.org