Post-quantum Cryptography

Cryptography in the era of quantum computers

The 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, uploading data to the cloud, or accessing work email remotely. Our research and engineering work has focused on protecting private information and communication from the possible threat of future quantum computers.

Quantum Computers will advance human knowledge in many fields. To balance that, we need to update some cryptography. Existing public-key cryptography (also known as asymmetric 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 have been studying cryptography approaches that appear to be resistant to an attacker who has access to a quantum computer, and we have been 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.

This work started in 2014, with our first paper published in 2015. In the intervening years we’ve submitted candidates to the NIST Post-Quantum Project and shepherded them through several rounds.

The key points: At the end of round 3, NIST picked for standardization CRYSTALS-Kyber for public-key encryption and key establishment, and CRYSTALS-Dilithium and two other algorithms for digital signatures. Meanwhile, ISO has approved FrodoKEM and two other algorithms for standardization.

What’s involved in post-quantum cryptography?

Any new cryptography has to integrate with existing internet 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 new cryptosystems also require careful cryptanalysis, to determine if there are any weaknesses that an adversary could exploit. 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 keep moving quickly because we don’t know exactly 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.

Crypto libraries, protocol integrations, and other resources

We are proud to participate in the Open Quantum Safe project where we help develop the liboqs library which is designed to further post-quantum cryptography. Additional information, protocol integrations, and related releases can be found on those sites.

Post-Quantum Crypto VPN

A fork of OpenVPN integrated with post-quantum cryptography to enable testing and experimentation with these algorithms.

Post-Quantum SSH

A fork of OpenSSH 7.7 that adds quantum-resistant key exchange and signature algorithms.

NIST Post-Quantum Project

We focused first on the NIST Post-Quantum Project, which asked for cryptographers around the world to submit candidates for subsequent peer review and analysis. Our team is worked 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 worked on two collaborations for key exchange, and one for signatures, as well as providing code in support of a second signature system. Each proposal had different strengths and weaknesses, and each was built upon a different mathematical “hard problem.” with different trade-offs regarding performance and key size. 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.

FrodoKEM

FrodoKEM is based upon the Learning with Errors problem, which is, in turn, based upon lattices.

SIKE

SIKE (Supersingular Isogeny Key Encapsulation) uses arithmetic operations of elliptic curves over finite fields to build a key exchange.

Picnic

Picnic is a public-key digital signature algorithm, based on a zero-knowledge proof system and symmetric key primitives.

qTESLA

qTESLA is a post-quantum signature scheme based upon the Ring Learning With Errors (R-LWE) problem.

 

Tell us what you think

Our community will only be able to come to a consensus on the right approach through open discussion and feedback. We would like you to test and verify our ideas. Please download, use, and provide feedback on our libraries and protocol integrations. You can talk to us at [email protected]

Research Team