Quantum-safe Cryptography Algorithms

Quantum-safe (sometimes also called “post-quantum”) cryptography is the design and implementation of protocols that are believed to be secure against the added computational capabilities of quantum computers. The two quantum algorithms that cause problems for current cryptography are Grover’s algorithm and Shor’s algorithm. Grover’s algorithm allows one to brute-force search a list in time that is smaller than the size of the list. This algorithm mostly affects the security of symmetric-key primitives (e.g. AES, SHA-256, etc.) and the protection against it generally requires one to simply double the key size. Shor’s algorithm, on the other hand, is more troublesome for the security of certain public-key primitives (e.g. RSA, EC-DSA, etc.). To withstand Shor’s algorithm, the key sizes of these schemes would need to increase exponentially, which would render them practically useless.

Old and new cryptography on the same stage - From left to right: Tom Geller, Whitfield Diffie, Vinton G. Cerf, Adi Shamir, Vadim Lyubashevsky, Gregor Seiler. © Heidelberg Laureate Forum Foundation / Flemming

The field of quantum-safe cryptography deals with building public-key cryptography, which can be implemented on standard devices, that can resist quantum attacks. While quantum computers have the potential to devastatingly solve certain mathematical problems, there are many other problems that have been studied for several decades for which we don’t believe that quantum algorithms are at all helpful. Some of these problems come from the mathematical areas of lattices, codes, isogenies, and multivariate equations. Migrating to quantum-safe cryptography requires us to first design efficient foundational primitives based on the hardness of such problems, and later combine them into various protocols.

A current central research objective of our scientists is the design, implementation, and standardization of new quantum-safe cryptographic algorithms that can replace the classical non-quantum-safe ones. These include encryption and signature schemes that are currently undergoing standardization by NIST, as well as more advanced schemes from the area of privacy-preserving cryptography.

NIST Post-Quantum Standardization

From 2017 to 2022, NIST went through three rounds of a selection process to produce standards for quantum-safe encryption and digital signature schemes. There were 69 initial submissions that were judged on the basis of security and performance. The third and final round was completed at the end of March, and NIST announced the selection of new algorithms to recommend for standardization in July 2022. 

IBM Research scientists have been involved in creating many quantum safe algorithm designs. Below are the algorithms with IBM Research leadership and contributions in the NIST Post-Quantum Cryptography (PQC) finals and the selected standards.

IBM Research Scientists' Involvement in NIST PQC Public-Key Encryption/KEMs Finalists

CRYSTALS-Kyber

🥇 NIST selected primary standard

Kyber is a public key encryption / key establishment mechanism based on the hardness of finding short vectors in Euclidean lattices. More specifically, Kyber is based on the module learning with errors problem. It offers high security, balanced key and ciphertext sizes, and leading performance on a diverse range of platforms.

IBM Research scientists Vadim Lyubashevsky and Gregor Seiler contributed to the design and implementation of Kyber.

Learn more

IBM Research Scientists' Involvement in NIST PQC Digital Signature Finalists

CRYSTALS-Dilithium

🥇 NIST selected primary standard

Similar to Kyber, Dilithium is a lattice-based signature scheme based on the module learning with errors and module short integer solution problems. Its construction follows the Fiat-Shamir with aborts paradigm that was invented by IBM Researcher Vadim Lyubashevsky. Unlike other signature schemes, Dilithium lends itself to high-confidence secure implementations and still offers very fast performance in optimized implementations. The combined key and signature size of Dilithium is the second smallest in the competition.

The Dilithium team is led by Vadim Lyubashevsky, and Gregor Seiler also contributed to the design and led the implementation of the scheme.

Learn more

Falcon

🥈 NIST selected standard

Falcon is also a lattice-based signature scheme. Compared to Dilithium, Falcon uses a different design paradigm and offers shorter key and signature sizes at the cost of higher implementation complexity and slightly worse performance, especially on constrained devices. The combined key and signature size of Falcon is the smallest in the competition.

IBM Researchers Vadim Lyubashevsky and Gregor Seiler contributed to the design of Falcon.

Learn more

SPHINCS+

🥈 NIST selected standard

Relying only on the security of standard hash functions, SPHINCS+ is the most conservative signature scheme. This strong security guarantee comes at the cost of a somewhat large signature size or a somewhat large signing time, depending on which variant of SPHINCS+ is used. SPHINCS+ is closely related to the stateful eXtended Merkle Signature Scheme (XMSS), which is standardized by the IETF and recommended by NIST. Unlike XMSS, SPHINCS+ is not stateful, which makes SPHINCS+ suitable for general use.

Ward Beullens contributed to the design of SPHINCS+ since the third round of the NIST process.

Learn more