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 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 and conducted in collaboration with academic and industry partners; our implementations are open source. The goal is robust, trusted, tested and standardized post-quantum cryptography.

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 the rounds.

At the end of round 3, NIST picked for standardization CRYSTALS-Kyber for public-key encryption and key establishment, and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for digital signatures. At the same time, 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 that the fact that someone could store existing encrypted data and decrypt it in the future once they have a quantum computer, and our task becomes even more urgent.

Active PQC Algorithm Research

FrodoKEM

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

SQISign

SQISign is a compact post-quantum signature scheme, based upon isogeny graphs of supersingular elliptic curves. SQISign is a candidate in the NIST PQC Signature project. 

 

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 and many protocol integration projects (e.g., OpenSSL for TLS and OpenSSH for SSH), which are designed to further post-quantum cryptography. We’ve also created a fork of OpenVPN (note that this project is several years old and is not being maintained) to demonstrate how PQC can be used on VPN tunnels.

NIST Post-Quantum Project

Microsoft Research participated in the NIST Post-Quantum Project, which asked cryptographers around the world to submit candidates for subsequent peer review and analysis. Our team worked with academic and industry partners on four candidates for cryptography systems that we believed could 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 was 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.

We include these links to the three algorithms that are no longer active for historical purposes, for researchers who may be interested in the original submissions. In the summer of 2022, researchers found a catastrophic break in SIKE. It is important to note that the version below is the broken version.

SIKE

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

Picnic

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

qTESLA

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

NIST NCCoE PQC Migration Project

We are currently participating in the NIST Cybersecurity Center of Excellence (NCCoE) PQC Migration project, where we work with industrial and government partners to build vulnerable algorithm detection tools and test the interoperability and performance of quantum safe protocols and applications. More details can be found in the reports available on the NCCoE project page: Migration to Post-Quantum Cryptography | NCCoE

Tell us what you think

You can talk to us at msrsc@microsoft.com

Research Team