< draft-hoffman-c2pq-04.txt   draft-hoffman-c2pq-05.txt >
Network Working Group P. Hoffman Network Working Group P. Hoffman
Internet-Draft ICANN Internet-Draft ICANN
Intended status: Informational August 13, 2018 Intended status: Informational May 21, 2019
Expires: February 14, 2019 Expires: November 22, 2019
The Transition from Classical to Post-Quantum Cryptography The Transition from Classical to Post-Quantum Cryptography
draft-hoffman-c2pq-04 draft-hoffman-c2pq-05
Abstract Abstract
Quantum computing is the study of computers that use quantum features Quantum computing is the study of computers that use quantum features
in calculations. For over 20 years, it has been known that if very in calculations. For over 20 years, it has been known that if very
large, specialized quantum computers could be built, they could have large, specialized quantum computers could be built, they could have
a devastating effect on asymmetric classical cryptographic algorithms a devastating effect on asymmetric classical cryptographic algorithms
such as RSA and elliptic curve signatures and key exchange, as well such as RSA and elliptic curve signatures and key exchange, as well
as (but in smaller scale) on symmetric cryptographic algorithms such as (but in smaller scale) on symmetric cryptographic algorithms such
as block ciphers, MACs, and hash functions. There has already been a as block ciphers, MACs, and hash functions. There has already been a
skipping to change at page 2, line 7 skipping to change at page 2, line 7
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on February 14, 2019. This Internet-Draft will expire on November 22, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
skipping to change at page 2, line 38 skipping to change at page 2, line 38
1.2. Executive Summary . . . . . . . . . . . . . . . . . . . . 3 1.2. Executive Summary . . . . . . . . . . . . . . . . . . . . 3
1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Not Covered: Post-Quantum Cryptographic Algorithms . . . 5 1.4. Not Covered: Post-Quantum Cryptographic Algorithms . . . 5
1.5. Not Covered: Quantum Cryptography . . . . . . . . . . . . 5 1.5. Not Covered: Quantum Cryptography . . . . . . . . . . . . 5
1.6. Where to Read More . . . . . . . . . . . . . . . . . . . 5 1.6. Where to Read More . . . . . . . . . . . . . . . . . . . 5
2. Brief Introduction to Quantum Computers . . . . . . . . . . . 6 2. Brief Introduction to Quantum Computers . . . . . . . . . . . 6
2.1. Quantum Computers that Recover Cryptographic Keys . . . . 7 2.1. Quantum Computers that Recover Cryptographic Keys . . . . 7
3. Physical Designs for Quantum Computers . . . . . . . . . . . 7 3. Physical Designs for Quantum Computers . . . . . . . . . . . 7
3.1. Qubits, Error Detection, and Error Correction . . . . . . 8 3.1. Qubits, Error Detection, and Error Correction . . . . . . 8
3.2. Promising Physical Designs for Quantum Computers . . . . 8 3.2. Promising Physical Designs for Quantum Computers . . . . 8
3.3. Challenges for Physical Designs . . . . . . . . . . . . . 8 3.3. Challenges for Physical Designs . . . . . . . . . . . . . 9
4. Quantum Computers and Public Key Cryptography . . . . . . . . 9 4. Quantum Computers and Public Key Cryptography . . . . . . . . 9
4.1. Explanation of Shor's Algorithm . . . . . . . . . . . . . 10 4.1. Explanation of Shor's Algorithm . . . . . . . . . . . . . 10
4.2. Properties of Large, Specialized Quantum Computers Needed 4.2. Properties of Large, Specialized Quantum Computers Needed
for Recovering RSA Public Keys . . . . . . . . . . . . . 10 for Recovering RSA Public Keys . . . . . . . . . . . . . 10
5. Quantum Computers and Symmetric Key Cryptography . . . . . . 10 5. Quantum Computers and Symmetric Key Cryptography . . . . . . 11
5.1. Properties of Large, Specialized Quantum Computers Needed 5.1. Properties of Large, Specialized Quantum Computers Needed
for Recovering Symmetric Keys . . . . . . . . . . . . . . 12 for Recovering Symmetric Keys . . . . . . . . . . . . . . 12
5.2. Properties of Large, Specialized Quantum Computers for 5.2. Properties of Large, Specialized Quantum Computers for
Computing Hash Collisions . . . . . . . . . . . . . . . . 12 Computing Hash Collisions . . . . . . . . . . . . . . . . 12
6. Predicting When Useful Cryptographic Attacks Will Be Feasible 12 6. Predicting When Useful Cryptographic Attacks Will Be Feasible 12
6.1. Proposal: Public Measurements of Various Quantum 6.1. Proposal: Public Measurements of Various Quantum
Technologies . . . . . . . . . . . . . . . . . . . . . . 13 Technologies . . . . . . . . . . . . . . . . . . . . . . 13
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14
8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.1. Normative References . . . . . . . . . . . . . . . . . . 15 10.1. Normative References . . . . . . . . . . . . . . . . . . 15
10.2. Informative References . . . . . . . . . . . . . . . . . 15 10.2. Informative References . . . . . . . . . . . . . . . . . 15
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 16 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 17
1. Introduction 1. Introduction
Early drafts of this document use "@@@@@" to indicate where the Early drafts of this document use "@@@@@" to indicate where the
editor particularly want input from reviewers. The editor welcomes editor particularly want input from reviewers. The editor welcomes
all types of review, but the areas marked with "@@@@@" are in the all types of review, but the areas marked with "@@@@@" are in the
most noticeable need of new material. (The editor particularly most noticeable need of new material. (The editor particularly
appreciates new material that comes with references that can be appreciates new material that comes with references that can be
included in this document as well.) included in this document as well.)
1.1. Disclaimer 1.1. Disclaimer
**** This is an early version of this draft. **** As such, it has had **** This is still an early version of this draft. **** As such, it
little in-depth review in the cryptography community. Statements in has had only some review in the cryptography community. Statements
this document might be wrong; given that the entire document is about in this document might be wrong; given that the entire document is
cryptography, those wrong statements might have significant security about cryptography, those wrong statements might have significant
problems associated with them. security problems associated with them.
Readers of this document should not rely on any statements in this Readers of this document should not rely on any statements in this
version of this draft. As the draft gets more input from the version of this draft. As the draft gets more input from the
cryptography community over time, this disclaimer will be softened cryptography community over time, this disclaimer will be softened
and eventually eliminated. and eventually eliminated.
1.2. Executive Summary 1.2. Executive Summary
The development of quantum computers that can recover private or The development of quantum computers that can recover private or
secret keys in classical algorithms at the key sizes commonly used secret keys in classical algorithms at the key sizes commonly used
skipping to change at page 6, line 11 skipping to change at page 6, line 11
the overview article at <https://en.wikipedia.org/wiki/ the overview article at <https://en.wikipedia.org/wiki/
Quantum_computing> and the timeline of quantum computing developments Quantum_computing> and the timeline of quantum computing developments
at <https://en.wikipedia.org/wiki/Timeline_of_quantum_computing>. at <https://en.wikipedia.org/wiki/Timeline_of_quantum_computing>.
[NielsenChuang] is a well-regarded college textbook on quantum [NielsenChuang] is a well-regarded college textbook on quantum
computers. Prerequisites for understanding the book include linear computers. Prerequisites for understanding the book include linear
algebra and some quantum physics; however, even without those, a algebra and some quantum physics; however, even without those, a
reader can probably get value from the introductory material in the reader can probably get value from the introductory material in the
book. book.
A good overview of the current status of quantum computing in general
is [ProgressProspects].
[QCPolicy] describes how the development of quantum computing affects
encryption policies.
[Turing50Youtube] is a good overview of the near-term and longer-term [Turing50Youtube] is a good overview of the near-term and longer-term
prospects for designing and building quantum computers; it is a video prospects for designing and building quantum computers; it is a video
of a panel discussion by quantum hardware and software experts given of a panel discussion by quantum hardware and software experts given
at the ACM's Turing 50 lecture. at the ACM's Turing 50 lecture.
@@@@@ Maybe add more references that might be useful to non-experts. @@@@@ Maybe add more references that might be useful to non-experts.
2. Brief Introduction to Quantum Computers 2. Brief Introduction to Quantum Computers
A quantum computer is a computer that uses quantum bits (qubits) in A quantum computer is a computer that uses quantum bits (qubits) in
skipping to change at page 10, line 22 skipping to change at page 10, line 28
@@@@@ Give the steps for applying Shor's algorithm to 2048-bit RSA. @@@@@ Give the steps for applying Shor's algorithm to 2048-bit RSA.
Describe how many rounds of the quantum subroutine would likely be Describe how many rounds of the quantum subroutine would likely be
needed. Describe how many rounds of the classical loop would likely needed. Describe how many rounds of the classical loop would likely
be needed. be needed.
[ResourceElliptic] gives concrete estimates of the resources needed [ResourceElliptic] gives concrete estimates of the resources needed
to build a quantum computer to compute elliptic curve discrete to build a quantum computer to compute elliptic curve discrete
logarithms. It shows that for the common P-256 elliptic curve, 2330 logarithms. It shows that for the common P-256 elliptic curve, 2330
logical qubits and over 10^11 Toffoli gates. logical qubits and over 10^11 Toffoli gates.
[PrimeFactAnneal] describes a method of converting the integer
factorization problem to one that can be executed on an adiabatic
quantum computer. Adiabatic quantum computers are already available
today, such as those from D-Wave Systems. Note that this method is
not a way to run Shor's algorithm on an adiabatic quantum computer.
4.2. Properties of Large, Specialized Quantum Computers Needed for 4.2. Properties of Large, Specialized Quantum Computers Needed for
Recovering RSA Public Keys Recovering RSA Public Keys
Researchers have built small quantum computers that implement Shor's Researchers have built small quantum computers that implement Shor's
algorithm, factoring numbers with four or five bits. These are used algorithm, factoring numbers with four or five bits. These are used
to show that Shor's algorithm is possible to realize in actual to show that Shor's algorithm is possible to realize in actual
hardware. (Note, however, that [PretendingFactor] indicates that hardware. (Note, however, that [PretendingFactor] indicates that
these experiments may have taken shortcuts that prevent them from these experiments may have taken shortcuts that prevent them from
indicating real Shor designs.) indicating real Shor designs.)
skipping to change at page 12, line 15 skipping to change at page 12, line 29
computers, this will make doing all the calculations needed to computers, this will make doing all the calculations needed to
break an AES-128 key take so long as to be infeasible. break an AES-128 key take so long as to be infeasible.
5.1. Properties of Large, Specialized Quantum Computers Needed for 5.1. Properties of Large, Specialized Quantum Computers Needed for
Recovering Symmetric Keys Recovering Symmetric Keys
[ApplyingGrover] estimates that a quantum computer that can determine [ApplyingGrover] estimates that a quantum computer that can determine
the secret keys for AES-128 would require 2953 correlated qubits and the secret keys for AES-128 would require 2953 correlated qubits and
2.74 * 2^86 gates. 2.74 * 2^86 gates.
[GoverSDES] shows how to use Grover's algorithm to search for keys in
SDES, a simplifed version of the DES encryption algorithm.
5.2. Properties of Large, Specialized Quantum Computers for Computing 5.2. Properties of Large, Specialized Quantum Computers for Computing
Hash Collisions Hash Collisions
@@@@@ More goes here. Also, discuss how Grover's algorithm does not @@@@@ More goes here. Also, discuss how Grover's algorithm does not
appear to be useful for computing preimages (or say how it might be appear to be useful for computing preimages (or say how it might be
used). used).
6. Predicting When Useful Cryptographic Attacks Will Be Feasible 6. Predicting When Useful Cryptographic Attacks Will Be Feasible
If quantum computers that perform useful cryptographic attacks can be If quantum computers that perform useful cryptographic attacks can be
skipping to change at page 15, line 41 skipping to change at page 16, line 9
[EstimatingPreimage] [EstimatingPreimage]
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent,
A., and J. Schanck, "Estimating the cost of generic A., and J. Schanck, "Estimating the cost of generic
quantum pre-image attacks on SHA-2 and SHA-3", 2016, quantum pre-image attacks on SHA-2 and SHA-3", 2016,
<https://eprint.iacr.org/2016/992>. <https://eprint.iacr.org/2016/992>.
[FindCollisions] [FindCollisions]
Bernstein, D., "Quantum algorithms to find collisions", Bernstein, D., "Quantum algorithms to find collisions",
2017, <https://blog.cr.yp.to/20171017-collisions.html>. 2017, <https://blog.cr.yp.to/20171017-collisions.html>.
[GoverSDES]
Denisenko, D. and M. Nikitenkova, "Application of Grover's
Quantum Algorithm for SDES Key Searching", 2018.
[LowResource] [LowResource]
Bernstein, D., Fiassse, J., and M. Mosca, "A low-resource Bernstein, D., Fiassse, J., and M. Mosca, "A low-resource
quantum factoring algorithm", 2017, quantum factoring algorithm", 2017,
<https://eprint.iacr.org/2017/352.pdf>. <https://eprint.iacr.org/2017/352.pdf>.
[MariantoniYoutube] [MariantoniYoutube]
Mariantoni, M., "Building a Superconducting Quantum Mariantoni, M., "Building a Superconducting Quantum
Computer", 2014, Computer", 2014,
<https://www.youtube.com/watch?v=wWHAs--HA1c>. <https://www.youtube.com/watch?v=wWHAs--HA1c>.
skipping to change at page 16, line 21 skipping to change at page 16, line 39
Chen, L. and et. al, "Report on Post-Quantum Chen, L. and et. al, "Report on Post-Quantum
Cryptography", 2016, Cryptography", 2016,
<http://nvlpubs.nist.gov/nistpubs/ir/2016/ <http://nvlpubs.nist.gov/nistpubs/ir/2016/
NIST.IR.8105.pdf>. NIST.IR.8105.pdf>.
[PretendingFactor] [PretendingFactor]
Smolin, J., Vargo, A., and J. Smolin, "Pretending to Smolin, J., Vargo, A., and J. Smolin, "Pretending to
factor large numbers on a quantum computer", 2013, factor large numbers on a quantum computer", 2013,
<https://arxiv.org/abs/1301.7007>. <https://arxiv.org/abs/1301.7007>.
[PrimeFactAnneal]
Jiang, S., Britt, K., McCaskey, A., Humble, T., and S.
Kais, "Quantum Annealing for Prime Factorization", 2018,
<https://www.nature.com/articles/s41598-018-36058-z>.
[ProgressProspects]
The National Acadamies Sciences Engineering Medicine,
"Quantum Computing: Progress and Prospects (2019)", n.d.,
<https://www.nap.edu/catalog/25196/
quantum-computing-progress-and-prospects>.
[QCPolicy]
Princeton University Center for Information Technology
Policy, "Implications of Quantum Computing for Encryption
Policy", 2019, <https://carnegieendowment.org/2019/04/25/
implications-of-quantum-computing-for-encryption-policy-
pub-78985>.
[QuantumSearch] [QuantumSearch]
Grover, L., "From Schrodinger's Equation to the Quantum Grover, L., "From Schrodinger's Equation to the Quantum
Search Algorithm", 2001, Search Algorithm", 2001,
<https://arxiv.org/abs/quant-ph/0109116>. <https://arxiv.org/abs/quant-ph/0109116>.
[ResourceElliptic] [ResourceElliptic]
Roetteler, M., Naehrig, M., Svore, K., and K. Lauter, Roetteler, M., Naehrig, M., Svore, K., and K. Lauter,
"Quantum Resource Estimates for Computing Elliptic Curve "Quantum Resource Estimates for Computing Elliptic Curve
Discrete Logarithms", 2017, Discrete Logarithms", 2017,
<https://eprint.iacr.org/2017/598>. <https://eprint.iacr.org/2017/598>.
 End of changes. 14 change blocks. 
14 lines changed or deleted 51 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/