< 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/ |