Building a security standard for a post-quantum future

The world stands to gain immeasurable computing power from fully-realized quantum computers. These machines would render many classically hard problems efficient to solve, surpassing the power of decades of algorithm development for classical computers.

But with the new capabilities come some unfortunate drawbacks: several of these classically hard problems form the foundation of 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 disastrous hypothetical, cryptographers working in a field called “post-quantum cryptography” are attempting to design new algorithms and standards to thwart quantum codebreakers.

Patrick C. Fischer Development Professor in Theoretical Computer Science Chris Peikert has worked on many of the projects that are now at the leading edge of this area. Together with a team of eleven other researchers, he’s submitted a cryptographic scheme as a proposed standard to the NIST Post-Quantum Cryptography project. Called FrodoKEM, this family of encryption algorithms is designed to be a conservative and practical implementation of one of the most-studied approaches in the post-quantum cryptography field.

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.

Lattices are Peikert’s area of specialty. They’re simple but surprisingly rich geometric structures that represent multidimensional, repeating grids of points. The security of lattice-based crypto schemes rests on how easy it is to get lost in one that has hundreds of dimensions.

At its heart, lattice-based encryption works by starting from a random point in a lattice and adding some small “error” to arrive at a new location somewhere nearby. It’s exceedingly difficult to find the original lattice point if you’re only given its “noisy” version, because you must search across hundreds of dimensions. The lattice point acts as the private key and the “noisy” version is the public key.

The core of FrodoKEM is a public-key encryption scheme called FrodoPKE. This scheme implements an efficient LWE-based public-key scheme that was developed in part by Peikert in 2011. This implementation is more compact than prior LWE schemes, with key sizes up to 10 times smaller than prior, similar systems (also developed by Peikert and collaborators) while providing stronger concrete security levels.

One tactic that sets FrodoKEM apart is its use of “algebraically unstructured” lattices, as opposed to algebraic ones that many other proposals rely on for efficiency. This lack of structure comes at some cost in performance, but is still practical for most of today’s devices, networks, and applications, and offers a hedge against the possibility of future attacks against algebraic lattices.

FrodoKEM offers several advantages over other systems built on LWE and related problems. For one, it’s easy and compact to implement, requiring only about 250 lines of plain C code for the optimized implementation. Although its public keys and ciphertexts are larger than traditional cryptographic algorithms and some other post-quantum candidates, it’s still small enough to be compatible with other methods for use in hybrid schemes. Additionally, its implementation is resistant to a class of threats called “side-channel attacks” that other post-quantum systems can be difficult to protect against.

Since the trajectory of quantum computing is so unpredictable, and a cryptographic system would ideally have a lifetime of several decades, the FrodoKEM researchers argue that any post-quantum standard should err on the side of security and simplicity over performance and optimization. FrodoKEM was built around this philosophy.

The submission process for this new class of NIST standards will unfold over the coming years; Peikert presented this system at their first NIST Post-Quantum Cryptography workshop in early April. The project is a collaboration between researchers and engineers at CWI, Google, McMaster University, Microsoft Research, NXP Semiconductors, Stanford University, and University of Michigan.