Cryptography in the era of quantum computersThe private communication of individuals and organizations is protected online by cryptography. Cryptography protects our information as it travels over and is stored on the internet—whether making a purchase from an online store or accessing work email remotely.
Our research and engineering work focuses on how private information and communications will be protected when more powerful computers, such as quantum computers, which can break that cryptography are available.
Existing public-key cryptography is based on the difficulty of factoring and the difficulty of calculating elliptic curve discrete logarithms. Because those two problems will be readily and efficiently solved by a sufficiently large-scale quantum computer, we are looking now at cryptography approaches that appear to be resistant to an attacker who has access to a quantum computer. we are developing cryptosystems whose security relies on different, hard mathematical problems that are resistant to being solved by a large-scale quantum computer.
Our work is open, open-source, and conducted in collaboration with academic and industry partners. The goal is robust, trusted, tested and standardized post-quantum cryptosystems.
What’s involved in post-quantum cryptography?Any new cryptography has to integrate with existing protocols, such as TLS. A new cryptosystem must weigh:
- The size of encryption keys and signatures
- The time required to encrypt and decrypt on each end of a communication channel, or to sign messages and verify signatures, and
- The amount of traffic sent over the wire required to complete encryption or decryption or transmit a signature for each proposed alternative.
The work of developing new cryptosystems that are quantum-resistant must be done openly, in full view of cryptographers, organizations, the public, and governments around the world, to ensure that the new standards emerging have been well vetted by the community, and to ensure that there is international support.
And lastly, we must do all this quickly because we don’t know when today’s classic cryptography will be broken. It’s difficult and time-consuming to pull and replace existing cryptography from production software. Add to all that the fact that someone could store existing encrypted data and unlock it in the future once they have a quantum computer, and our task becomes even more urgent.
NIST Post-Quantum ProjectWe are focused first on the NIST Post-Quantum Project, which asks for cryptographers around the world to submit candidates for subsequent peer review and analysis. Our team is working with academia and industry on four candidates for cryptography systems that can both withstand quantum computer capabilities, while still working with existing protocols.
Why four? We have been working on two collaborations for key exchange, and one for signatures, as well as providing code in support of a second signature system. Each proposal has different strengths and weaknesses, and each is built upon a different mathematical “hard problem.” Each may be appropriate for different scenarios where different trade-offs regarding performance and key size are preferred. Pursuing multiple candidates is also appropriate as the post-quantum cryptography field is young, and many years of cryptanalysis are needed to determine whether any post-quantum proposal is secure.