New NIST post-quantum standards make use of research by Prof. Chris Peikert

The National Institute of Standards and Technology (NIST) announced the first standard series of quantum-resistant cryptographic algorithms, a major development to secure digital information in a post-quantum world. The age of viable quantum computers is a major concern for cybersecurity researchers and policymakers, with threats of computing power strong enough to break through conventional encryption and access sensitive data. 

Two of the four algorithms selected for standardization are built on research results contributed by U-M Prof. Chris Peikert in 2008 and 2010. Crystals-Kyber was chosen as a primary option for key-establishment, and Falcon was chosen as a secondary digital signature standard for use cases that are too large for the primary algorithm Crystals-Dilithium.

The Falcon digital signature scheme is based directly on 2008 work by Peikert, Craig Gentry (then a PhD student at Stanford University), and Vinod Vaikuntanathan (then a PhD student at MIT). Their paper, “Trapdoors for hard lattices and new cryptographic constructions,” described simple and efficient “hash-and-sign” digital signature schemes, and identity-based encryption. 

Falcon is based on lattice cryptography, a set of problems currently considered too hard for quantum systems to crack and on which Peikert is an expert.

“Falcon is based on the theoretical framework of Gentry, Peikert, and Vaikuntanathan for lattice-based signature schemes,” Falcon’s authors write on their project’s webpage. “The underlying hard problem is the short integer solution problem (SIS) over NTRU lattices, for which no efficient solving algorithm is currently known in the general case, even with the help of quantum computers.”

The Kyber scheme for key-establishment builds on Peikert’s work with Vadim Lyubashevsky and Oded Regev (both at Tel-Aviv University at the time) on efficient ring-based lattice cryptography. Their paper, “On Ideal Lattices and Learning with Errors Over Rings,” described the first practical lattice-based public-key cryptosystem with an efficient security reduction.

Kyber also makes use of a ciphertext compression method introduced by Peikert in his 2009 work “Public-Key Encryption from the Worst-Case Shortest Vector Problem.” 

These and the other two standardized algorithms contribute to NIST’s ongoing post-quantum cryptographic standard, and will be finalized in roughly two years.