< draft-hoffman-c2pq-05.txt		draft-hoffman-c2pq-06.txt >
	Network Working Group P. Hoffman		Network Working Group P. Hoffman
	Internet-Draft ICANN		Internet-Draft ICANN
	Intended status: Informational May 21, 2019		Intended status: Informational November 25, 2019
	Expires: November 22, 2019		Expires: May 28, 2020
	The Transition from Classical to Post-Quantum Cryptography		The Transition from Classical to Post-Quantum Cryptography
	draft-hoffman-c2pq-05		draft-hoffman-c2pq-06
	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 November 22, 2019.		This Internet-Draft will expire on May 28, 2020.
	Copyright Notice		Copyright Notice
	Copyright (c) 2019 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
	skipping to change at page 2, line 30 ¶		skipping to change at page 2, line 30 ¶
	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
	described in the Simplified BSD License.		described in the Simplified BSD License.
	Table of Contents		Table of Contents
	1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3		1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
	1.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 3		1.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . 3
	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. Where to Read More . . . . . . . . . . . . . . . . . . . 5
	1.5. Not Covered: Quantum Cryptography . . . . . . . . . . . . 5		1.5. Not Covered: Post-Quantum Cryptographic Algorithms . . . 5
	1.6. Where to Read More . . . . . . . . . . . . . . . . . . . 5		1.6. Not Covered: Quantum Key Exchange . . . . . . . . . . . . 6
	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 . . . . . . . . . . . . . 9		3.3. Challenges for Physical Designs . . . . . . . . . . . . . 8
	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 . . . . . . 11		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 . . . . . . . . . . . . . . . . . . . . . . 15		9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14
	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 . . . . . . . . . . . . . . . . . . . . . . . . 17		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
	skipping to change at page 5, line 5 ¶		skipping to change at page 5, line 5 ¶
	Some papers discussing quantum computers and cryptanalysis say that		Some papers discussing quantum computers and cryptanalysis say that
	large, specialized quantum computers "break" algorithms in classical		large, specialized quantum computers "break" algorithms in classical
	cryptography. This paper does not use that terminology because the		cryptography. This paper does not use that terminology because the
	algorithms' strength will be reduced when large, specialized quantum		algorithms' strength will be reduced when large, specialized quantum
	computers exist, but not to the point where there is an immediate		computers exist, but not to the point where there is an immediate
	need to change algorithms.		need to change algorithms.
	The "^" symbol is used to indicate "the power of". The term "log"		The "^" symbol is used to indicate "the power of". The term "log"
	always means "logarithm base 2".		always means "logarithm base 2".
	1.4. Not Covered: Post-Quantum Cryptographic Algorithms		1.4. Where to Read More
			There are many reasonably accessible articles on Wikipedia, notably
			the overview article at <https://en.wikipedia.org/wiki/
			Quantum_computing> and the timeline of quantum computing developments
			at <https://en.wikipedia.org/wiki/Timeline_of_quantum_computing>.
			[NielsenChuang] is a well-regarded college textbook on quantum
			computers. Prerequisites for understanding the book include linear
			algebra and some quantum physics; however, even without those, a
			reader can probably get value from the introductory material in the
			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
			prospects for designing and building quantum computers; it is a video
			of a panel discussion by quantum hardware and software experts given
			at the ACM's Turing 50 lecture.
			@@@@@ Maybe add more references that might be useful to non-experts.
			1.5. Not Covered: Post-Quantum Cryptographic Algorithms
	This document discusses when an organization would want to consider		This document discusses when an organization would want to consider
	using post-quantum cryptographic algorithms, but definitely does not		using post-quantum cryptographic algorithms, but definitely does not
	delve into which of those algorithms would be best to use. Post-		delve into which of those algorithms would be best to use. Post-
	quantum cryptography is an active field of research; in fact, it is		quantum cryptography is an active field of research; in fact, it is
	much more active than the study of when we might want to transition		much more active than the study of when we might want to transition
	from classical to post-quantum cryptography.		from classical to post-quantum cryptography.
	Readers interested in post-quantum cryptographic algorithms will have		Readers interested in post-quantum cryptographic algorithms will have
	no problem finding many articles proposing such algorithms, comparing		no problem finding many articles proposing such algorithms, comparing
	skipping to change at page 5, line 27 ¶		skipping to change at page 6, line 4 ¶
	is the web site <http://pqcrypto.org/>. The Open Quantum Safe (OQS)		is the web site <http://pqcrypto.org/>. The Open Quantum Safe (OQS)
	project <https://openquantumsafe.org/> is developing and prototyping		project <https://openquantumsafe.org/> is developing and prototyping
	quantum-resistant cryptography. Another is the article on post-		quantum-resistant cryptography. Another is the article on post-
	quantum cryptography at Wikipedia: <https://en.wikipedia.org/wiki/		quantum cryptography at Wikipedia: <https://en.wikipedia.org/wiki/
	Post-quantum_cryptography>.		Post-quantum_cryptography>.
	Various organizations are working on standardizing the algorithms for		Various organizations are working on standardizing the algorithms for
	post-quantum cryptography. For example, the US National Institute of		post-quantum cryptography. For example, the US National Institute of
	Standards and Technology (commonly just called "NIST") is holding a		Standards and Technology (commonly just called "NIST") is holding a
	competition to evaluate post-quantum cryptographic algorithms.		competition to evaluate post-quantum cryptographic algorithms.
	NIST's description of that effort is currently at		NIST's description of that effort is currently at
	<http://csrc.nist.gov/groups/ST/post-quantum-crypto/>. Until		<http://csrc.nist.gov/groups/ST/post-quantum-crypto/>. Until
	recently, ETSI (the European Telecommunications Standards Institute)		recently, ETSI (the European Telecommunications Standards Institute)
	had a Quantum-Safe Cryptography (QSC) Industry Specification Group		had a Quantum-Safe Cryptography (QSC) Industry Specification Group
	(ISG) that worked on specifying post-quantum algorithms; see		(ISG) that worked on specifying post-quantum algorithms; see
	<http://www.etsi.org/technologies-clusters/technologies/quantum-safe-		<http://www.etsi.org/technologies-clusters/technologies/quantum-safe-
	cryptography> for results from this work.		cryptography> for results from this work.
	1.5. Not Covered: Quantum Cryptography		1.6. Not Covered: Quantum Key Exchange
	Other than in this section, this document does not cover "quantum
	cryptography". The field of quantum cryptography uses quantum
	effects in order to secure communication between users. Quantum
	cryptography is not related to cryptanalysis. The best known and
	extensively studied example of quantum cryptography is a quantum key
	exchange, where users can share a secret key while preventing an
	eavesdropper from obtaining the key.
	1.6. Where to Read More
	There are many reasonably accessible articles on Wikipedia, notably
	the overview article at <https://en.wikipedia.org/wiki/
	Quantum_computing> and the timeline of quantum computing developments
	at <https://en.wikipedia.org/wiki/Timeline_of_quantum_computing>.
	[NielsenChuang] is a well-regarded college textbook on quantum
	computers. Prerequisites for understanding the book include linear
	algebra and some quantum physics; however, even without those, a
	reader can probably get value from the introductory material in the
	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
	prospects for designing and building quantum computers; it is a video
	of a panel discussion by quantum hardware and software experts given
	at the ACM's Turing 50 lecture.
	@@@@@ Maybe add more references that might be useful to non-experts.		Other than in this section, this document does not cover "quantum key
			exchange", also called "quantum cryptography". The field of quantum
			key exchange uses quantum effects in order to secure communication
			between users. Quantum key exchange is not related to cryptanalysis.
	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
	quantum circuits to perform calculations. Quantum computers also use		quantum circuits to perform calculations. Quantum computers also use
	classical bits and regular circuits: most calculations in a quantum		classical bits and regular circuits: most calculations in a quantum
	computer are a mix of classical and quantum bits and circuits. For		computer are a mix of classical and quantum bits and circuits. For
	example, classical bits could be used for error correction or		example, classical bits could be used for error correction or
	controlling the behavior of physical components of the quantum		controlling the behavior of physical components of the quantum
	computer.		computer.
	skipping to change at page 11, line 38 ¶		skipping to change at page 11, line 34 ¶
	When it appears that it is feasible to build a large, specialized		When it appears that it is feasible to build a large, specialized
	quantum computer that can defeat a particular symmetric algorithm at		quantum computer that can defeat a particular symmetric algorithm at
	a particular key size, the proper response would be to use keys with		a particular key size, the proper response would be to use keys with
	twice as many bits. That is, if one is using the AES-128 algorithm		twice as many bits. That is, if one is using the AES-128 algorithm
	and there is a concern that an adversary might be able to build a		and there is a concern that an adversary might be able to build a
	large, specialized quantum computer that is designed to attack		large, specialized quantum computer that is designed to attack
	AES-128 keys, move to an algorithm that has keys twice as long as		AES-128 keys, move to an algorithm that has keys twice as long as
	AES-128, namely AES-256 (the block size used is not significant		AES-128, namely AES-256 (the block size used is not significant
	here).		here).
	It is currently expected that large, specialized quantum computers		By some estimates, large specialized quantum computers that implement
	that implement Grover's algorithm may be built before ones that		Grover's algorithm might be built before ones that implement Shor's
	implement Shor's algorithm are. There are two primary reasons for		algorithm are. There are two primary reasons for this:
	this:
	o Grover's algorithm is likely to be useful in areas other than		o Grover's algorithm is likely to be useful in areas other than
	cryptography. For example, a large, specialized quantum computer		cryptography. For example, a large, specialized quantum computer
	that implements Grover's algorithm might help create medicines by		that implements Grover's algorithm might help create medicines by
	speeding up complex problems that involve how proteins fold. @@@@@		speeding up complex problems that involve how proteins fold. @@@@@
	Add more likely examples and references here.		Add more likely examples and references here.
	o A large, specialized quantum computer that can recover AES-128		o A large, specialized quantum computer that can recover AES-128
	keys will likely be much smaller (and thus easier to build) than		keys will likely be much smaller (and thus easier to build) than
	one that implements Shor's algorithm for 256-bit elliptic curves		one that implements Shor's algorithm for 256-bit elliptic curves
	skipping to change at page 16, line 46 ¶		skipping to change at page 16, line 38 ¶
	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]		[PrimeFactAnneal]
	Jiang, S., Britt, K., McCaskey, A., Humble, T., and S.		Jiang, S., Britt, K., McCaskey, A., Humble, T., and S.
	Kais, "Quantum Annealing for Prime Factorization", 2018,		Kais, "Quantum Annealing for Prime Factorization", 2018,
	<https://www.nature.com/articles/s41598-018-36058-z>.		<https://www.nature.com/articles/s41598-018-36058-z>.
	[ProgressProspects]		[ProgressProspects]
	The National Acadamies Sciences Engineering Medicine,		The National Acadamies Sciences Engineering Medicine,
	"Quantum Computing: Progress and Prospects (2019)", n.d.,		"Quantum Computing: Progress and Prospects (2019)", 2019,
	<https://www.nap.edu/catalog/25196/		<https://www.nap.edu/catalog/25196/
	quantum-computing-progress-and-prospects>.		quantum-computing-progress-and-prospects>.
	[QCPolicy]		[QCPolicy]
	Princeton University Center for Information Technology		Princeton University Center for Information Technology
	Policy, "Implications of Quantum Computing for Encryption		Policy, "Implications of Quantum Computing for Encryption
	Policy", 2019, <https://carnegieendowment.org/2019/04/25/		Policy", 2019, <https://carnegieendowment.org/2019/04/25/
	implications-of-quantum-computing-for-encryption-policy-		implications-of-quantum-computing-for-encryption-policy-
	pub-78985>.		pub-78985>.
End of changes. 12 change blocks.
	49 lines changed or deleted		46 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/