IBM scientists help develop NIST’s quantum-safe standards

In 2016 contenders from all over the world submitted 69 cryptographic schemes for potential standardization. NIST later narrowed down the list of candidates over three stages, eventually shortlisting seven finalists — four for public key encryption and three for digital signatures.

At the end of a six-year-long process, three of the four chosen standards were developed by our team at IBM, in collaboration with a number of industry and academic partners. They include the CRYSTALS-Kyber public-key encryption and the CRYSTALS-Dilithium digital signature algorithms, which were chosen as primary standards. The Falcon digital signature algorithm was chosen as a standard to be used in situations where the use of Dilithium would be space-prohibitive.

CRYSTALS-Kyber was submitted* to NIST by ARM Limited’s Roberto Avanzi, NXP Semiconductors’ Joppe Bos, CWI Amsterdam’s Léo Ducas, Ruhr University Bochum’s Eike Kiltz, SRI International’s Tancrède Lepoint, IBM Quantum’s Vadim Lyubashevsky and Gregor Seiler, University of Waterloo’s John M. Schanck, MPI-SP & Radboud University’s Peter Schwabe, and ENS Lyon’s Damien Stehle. CRYSTALS-Dilithium was submitted by IBM Quantum’s Vadim Lyubashevsky and Gregor Seiler, CWI Amsterdam’s Léo Ducas, Ruhr University Bochum’s Eike Kiltz, SRI International’s Tancrède Lepoint, MPI-SP & Radboud University’s Peter Schwabe, ENS Lyon’s Damien Stehle, and Florida Atlantic University's Shi Bai. (*Affiliations listed at the time of submission.)Kyber“is a key encapsulation mechanism (KEM) whose security is based on the hardness of solving the learning-with-errors problem over module lattices, and is part of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite of algorithms.”¹

Dilithium, also a CRYSTALS algorithm, “is a digital signature scheme that has its security similarly based on the hardness of lattice problems over module lattices.”²

Falcon was submitted* to NIST by Rennes University’s Pierre-Alain Fouque, Brown University’s Jeffrey Hoffstein, École Normale Supérieure Paris’ and UC San Diego’s Paul Kirchner, IBM Quantum’s Vadim Lyubashevsky and Gregor Seiler, Cryptolog International’s Thomas Pornin, PQShield’s Thomas Prest, Thales's Cyber Defence Solutions’ Thomas Ricosset, Qualcomm’s William Whyte, and Algorand’s Zhenfei Zhang. (*Affiliations listed at the time of submission.)Falcon is another Current IBM scientist Ward Beullens contributed to digital signature SPHINCS+, the fourth protocol chosen for standardization.digital signature algorithm that is based on the hardness of finding short vectors in NTRU lattices. While Dilithium and Falcon are both lattice-based digital signature algorithms, they are complimentary in their applicability – Falcon has smaller parameters, while Dilithium is simpler to implement and deploy.

We think that quantum computing will be the next step in computation, augmenting classical computing resources, so that we can solve difficult and complex problems. While we’re still at the stage of building and exploring the possibilities of quantum technology, we also understand that today’s two most widely used current encryption schemes wouldn’t be secure against a fault tolerant, universal quantum computer.

This puts today’s sensitive information at peril, as attackers could harvest present-day data for later decryption.

Our security research team at IBM’s lab in Zurich has been working on quantum-safe cryptography for many years, and we are happy to see some of the cryptographic schemes we’ve co-developed with academic and industrial partners among those recognized by NIST.

However, the process of creating new quantum-safe standards is not yet over. NIST, the teams involved in the proposals, and the overall cryptographic community will further scrutinize and improve the chosen algorithms and turn them into standards over the next couple of years.

Even when standardized quantum-safe cryptography becomes a reality, there will still be a lot to do until vendors and the wider industry implement the new standards. The long path from standards to adoption will involve hard work from organizations to scrutinize their entire software inventory, identify the use of cryptography, quantify the risks and define and execute a strategy for becoming crypto-agile and migrating to quantum-safe solutions. For this reason, we’ve also established IBM Quantum Safe services in order to help our clients transition into this new era.

Why new cryptography is necessary in the quantum era

IBM has for years been an important global player in developing not just quantum-safe cryptography, but also — in tandem — quantum computers, themselves, and is therefore especially interested in ensuring the world is ready for the maturation of quantum computation.

Most of the encryption used today for securing internet communications dates back to cryptographic primitives created in the 1970s. They rely on mathematical problems such as factorization of large numbers, a calculation that is very easy to perform in the forward direction but extremely hard to invert.

In other words, given a pair of prime numbers, it’s easy to compute their product. However, if one starts with the product itself and is asked to find out the two original prime numbers, that task becomes unsolvable for even the best classical computers when the product is sufficiently large.

For quantum computers, however, factorization can in theory be solved — and solved within a few hours — with the help of Shor’s algorithm. That makes protocols like RSA an insufficient cryptographic scheme in a future where quantum computers have reached their full potential.

The same applies for other popular cryptographic methods based on the hardness of the discrete logarithm problem, including elliptic curve cryptography. All of them would be vulnerable to fault-tolerant quantum computers. That means that internet security protocols such as Transport Layer Security (TLS) that protect our private data — be it passwords or credit card details — on secure websites would no longer serve their purpose in the quantum era, leaving our data exposed to cyberattacks.

Lattice-based cryptography

In the quest for quantum-safe cryptographic primitives, researchers have been using different techniques to circumvent the new threats. Our team has focused mainly on Lattice-based cryptography is an approach for constructing security primitives. It is based on problems from an area of mathematics called “geometry of numbers.” Read more.lattice-based cryptography, an approach that emerged in the 1990s with two seminal papers: Brown University’s 1996 paper, NTRU: A ring-based public key cryptosystem, by Jeffrey Hoffstein, Jill Pipher and Joseph Silverman, which described a novel efficient cryptosystem they called NTRU (published in 1998 as part of the “Lecture Notes in Computer Science” book series).³

And IBM scientist Miklos Ajtai’s paper Generating Hard Instances of Lattice Problems,⁴ which proved a theoretical result showing that breaking lattice-based cryptosystems is most likely difficult, at least asymptotically. Twenty-six years later, these two papers form the basis of our schemes chosen by NIST: CRYSTALS-Kyber and CRYSTALS-Dilithium.

Lattice-based cryptography has become arguably the most widely studied area of quantum-safe cryptography protocols. That’s because the confidence in the concrete security of any cryptographic scheme is judged by the number of people looking at the constructions. This extensive public scrutiny gives us confidence in the long-term security of these primitives.

But quantum-safe lattice-based research does not end with encryption schemes and digital signatures. Researchers are also working on schemes based on the same hardness assumptions, to enable advanced functionality such as computation on encrypted data with what’s known as fully homomorphic encryption (FHE) and to provide key functionality for quantum-safe zero-trust environments.

We expect that lattice-based cryptography will soon become a central tool for cryptography and privacy. But even when quantum-safe cryptography standards are in place, organizations will have to act fast to move to a quantum-safe future. The world is becoming more acutely aware of the urgency of this transformation, as shown by the presidential mandate issued in the U.S. in January this year, ordering federal agencies to reassess their cyber preparedness for the coming quantum era. And the G7 has also agreed to cooperate on emerging technologies, including new quantum-safe cryptographic standards.

Although adopting quantum-safe cryptography at scale will be a decades-long process, some of our lattice-based schemes are entering the market in different products and services offered by IBM and others. The most recent example is As the industry's first quantum-safe system, IBM z16 is underpinned by lattice-based cryptography. With IBM z16 quantum-safe cryptography, businesses can future-ready their applications and data today.IBM z16, the industry’s first quantum-safe system, which uses CRYSTALS-Kyber and CRYSTALS-Dillithium as the underpinnings of its key encapsulation and digital signature capabilities.

IBM z16 is not the only user of our quantum-safe cryptography. Cloudflare integrated Kyber alongside other quantum-safe algorithms into CIRCL, the Cloudflare Interoperable, Reusable Cryptographic Library; Amazon now supports hybrid modes involving Kyber in their AWS Key Management Service; and in 2019 IBM introduced the world’s first quantum computing-safe tape drive using Kyber and Dilithium. Kyber has also been in use in hybrid mode in IBM Key Protect, IBM’s Public Cloud Key Management service, since 2020.

Moving from “safe” to “quantum safe”

The first step to get to a quantum-safe future is education: understanding quantum-safe cryptography and what the implications are for your organization. This can be a complex and long process, so we established IBM Quantum Safe services to help with awareness, guidance, and ultimately a risk assessment for an organization to make a decision on how to protect their systems and data well into the future. We employ the world’s most talented quantum physicists and cryptographic experts, and can therefore provide unique value to organizations interested in future-proofing their data encryption.