FrodoKEM

The FrodoKEM post-quantum cryptography project is a collaboration between researchers and engineers at CWI, Google, McMaster University, Microsoft Research, NXP Semiconductors, Stanford University, and University of Michigan.

FrodoKEM is a family of conservative yet practical post-quantum key encapsulation mechanisms with security based upon the hardness of the Learning With Errors (LWE) problem. LWE in turn relates to hard problems in “algebraically unstructured” lattices. The core of FrodoKEM is an LWE public-key encryption scheme called FrodoPKE. The research roots of this work extend back to 2005, when a seminal paper by Regev introduced the Learning With Errors problem, proved the hardness of certain instances of LWE against quantum algorithms, and defined an LWE-based public-key encryption scheme. Specifically, FrodoPKE is an improved instantiation and implementation of the Lindner-Peikert scheme proposed in 2011 which in turn follows Regev’s initial work on LWE. FrodoKEM achieves chosen-ciphertext (IND-CCA) security by applying a transformation to the IND-CPA-secure FrodoPKE scheme.

Complete details about the design and performance of FrodoKEM can be accessed in the links below.

The name FrodoKEM alludes to the fact that, unlike the related Ring-Learning With Errors (or R-LWE) cryptosystems, FrodoKEM does not use the algebraic ring structure central to these schemes (Frodo has gotten rid of the ring!).