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 the 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 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!).

The ISO/IEC JTC 1/SC 27/WG 2 is moving forward to standardize FrodoKEM in the next revision of the ISO/IEC 18033-2 Encryption Algorithms document.

FrodoKEM was originally submitted to the NIST Post-Quantum Cryptography Project, but after Round 3 was not selected for standardization by NIST.