Post-quantum Cryptography

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 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 proposed cryptosystems also requires 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 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 Project

We 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.

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.

Crypto libraries and protocol integrations

We have software libraries that implement the work for each of these post-quantum cryptosystems collaborations. Some libraries include optimizations for specific hardware platforms (such as Advanced RISC Machine (ARM)). We are also working to integrate each with common internet protocols so that we can test and further tune performance. We are proud to participate in liboqs and the Open Quantum Safe project, which are 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.

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 msrsc@microsoft.com

Research Team