Post-Quantum Cryptography Frodo-KEM

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.

Learn more about FrodoKEM:

FrodoKEM homepage
FrodoKEM GitHub

FrodoKEM is one component of Microsoft Research’s Post-Quantum Cryptography Project.

People

Portrait of Erdem Alkim

Erdem Alkim

Ondokuz Mayis University

Portrait of Joppe Bos

Joppe Bos

Researcher

NXP Semiconductors

Portrait of Léo Ducas

Léo Ducas

Researcher

Centrum Wiskunde & Informatica (CWI)

Portrait of Karen Easterbrook

Karen Easterbrook

Senior Director

Portrait of Patrick Longa

Patrick Longa

Senior Researcher

Portrait of Ilya Mironov

Ilya Mironov

Google

Portrait of Michael Naehrig

Michael Naehrig

Principal Researcher

Portrait of Valeria Nikolaenko

Valeria Nikolaenko

Portrait of Chris Peikert

Chris Peikert

Associate Professor

University of Michigan

Portrait of Ananth Raghunathan

Ananth Raghunathan

Senior Research Scientist

Google Brain

Portrait of Douglas Stebila

Douglas Stebila

Assistant Professor

McMaster University