“The Long Road Ahead to Transition to Post-Quantum Cryptography”
Communications of the ACM, January 2022, Vol. 65 No. 1, Pages 28-30
Security
By Brian LaMacchia
“Much of the post-quantum transition work that needs to be done can start now, even while we wait for algorithm and protocol standards to be updated.”
When we send encrypted information over a public communication channel, our security models must assume adversaries are recording that information in the hopes of being able to eventually break the encryption and exploit the underlying plaintext. An encryption algorithm believed to be secure today could cease to be in the future due to new advances in number theory, new cryptanalytic techniques, or even new methods of computing. It is this last risk, in particular the risk posed by the potential future development of large-scale, fault-tolerant quantum computers, that is currently the focus of much of the international cryptographic research community, driven by a worldwide open competition to select and standardize new post-quantum (a.k.a. quantum-resistant) public-key cryptographic algorithms. As we approach the first output milestone in that competition, it is critical for everyone in our industry to be aware of the coming algorithm transition, the impact it will have on existing and future systems, and the research and engineering work still needed to make the transition to post-quantum cryptography (PQC) possible.
From mobile communications to online banking to personal data privacy, literally billions of Internet users rely on cryptography every day to ensure private communications and data stay private. Indeed, the emergence and growth of the public Internet and electronic commerce was arguably enabled by the invention of public-key cryptography. The critical advantage offered by public-key cryptography is that it allows two parties who have never communicated previously to nevertheless establish a secure, private, communication channel over a non-private network (that is, the Internet). Public-key cryptography is also the technology that enables digital signatures, which are widely used to protect software and application updates, online contracts, and electronic identity credentials.
Since 1994, when Peter Shor of AT&T Bell Laboratories developed the polynomial-time quantum factoring algorithm that now bears his name, we have known that all our widely deployed public-key cryptographic algorithms can be attacked efficiently with the aid of a cryptographically relevant (that is, “big enough”) quantum computer. Whether such a quantum computer could even be built was and still is a purely theoretical question. However, while today’s quantum computers are not big enough or stable enough to threaten our current algorithms, they point the way to future devices that could. Further, while a cryptographically relevant quantum computer may not be realized for a decade or longer, its future existence is a threat to the security of information we send and receive today due to the ability to record content now for later exploitation. The threat of record now, exploit later means we need to transition to using quantum-resistant public-key algorithms well in advance of the availability of cryptographically relevant quantum computers.
Acknowledging the threat to existing cryptography posed by future quantum computers, the U.S. National Security Agency (NSA) first warned the public of the need to transition to PQC algorithms in August 2015, and in 2017 the U.S. National Institute of Standards and Technology (NIST) launched its PQC Standardization activity to select new quantum-resistant public-key algorithms. As with its prior algorithm competitions that resulted in the AES block cipher and SHA-3 hash function standards, NIST solicited PQC algorithm proposals and cryptanalysis of them from around the world. Chosen algorithms win the “prize” of being standardized as U.S. Federal Information Processing Standards (FIPS) and then being used as replacement algorithms just about everywhere public-key cryptography is used.
About the Author:
Brian LaMacchia is a Distinguished Engineer at Microsoft Corporation and heads the Security and Cryptography team at Microsoft Research, Redmond, WA, USA.
See Also:
- NIST Announces First Four Quantum-Resistant Cryptographic Algorithms: Federal agency reveals the first group of winners from its six-year competition. July 05, 2022
