NIST finalists for post-quantum security standards include research results developed by Prof. Chris Peikert

Quantum computers, which hold the potential to solve certain computational problems much more quickly than classical computers can, are in development in labs around the world. Once viewed as the stuff of science fiction, these highly complex systems are slowly moving toward realizing their potential as difficult technical hurdles are being knocked down.

Because quantum computers may be able to quickly solve problems that no classical computer can solve in any feasible amount of time, they could be the key to unlocking many computational challenges, such as in simulations for studying the behavior of atoms and particles under unique circumstances, for drug development, for climate modeling, for solar capture, and for materials discovery. 

But with the new capabilities come unfortunate drawbacks: several of these classically hard problems form the foundation of our current encryption techniques. In fact, some of the problems quantum computers are the most effective at solving are the ones that keep our digital communications secure.

A large quantum computer could retroactively decrypt almost all internet communication ever recorded.

To prepare for this possibility, in 2017 the National Institute of Standards and Technology (NIST) initiated a multi-stage process to standardize one or more quantum-resistant public-key cryptographic algorithms; in other words, a set of post-quantum cybersecurity standards.

Last week, NIST revealed its selection of seven finalist submissions and eight alternates for the third round of its post-quantum cryptography standardization process.

Chris Peikert, the Patrick C. Fischer Development Professor of Theoretical Computer Science at Michigan, is a primary designer and author of one of the alternates, called FrodoKEM. FrodoKEM is built on a problem called Learning With Errors (LWE), which in turn is built on the problem of correcting errors in a structure called a lattice.

In addition, two of the finalists, Falcon and Kyber, are directly based on Peikert’s research: Falcon uses the “GPV” paradigm for digital signatures, and Kyber is closely related to his work on Ring-LWE cryptography and efficient ring-based cryptosystems.

All of these solutions rely on the apparent difficulty of finding special points in multi-dimensional grids called lattices, as opposed to “hard”  algebraic formulas that can be efficiently solved by quantum computers.

NIST is allowing finalist submissions to provide updated specifications and implementations by October 1, 2020, after which there will be a period of evaluation lasting 12-18 months. When that process concludes, NIST expects to select one of the finalists or alternate solutions as a public-key encryption and digital signature standard.