FrodoKEM: Learning with errors key encapsulation

Size (in bytes) of inputs and outputs of FrodoKEM.


This submission defines a family of key-encapsulation mechanisms (KEMs), collectively called FrodoKEM. The FrodoKEM schemes are designed to be conservative yet practical post-quantum constructions whose security derives from cautious parameterizations of the well-studied learning with errors problem, which in turn has close connections to conjectured-hard problems on generic, “algebraically unstructured” lattices.

Concretely, FrodoKEM is designed for IND-CCA security at two levels:

  • FrodoKEM-640, which targets Level 1 in the NIST call for proposals (matching or exceeding the brute-force security of AES-128), and
  • FrodoKEM-976, which targets Level 3 in the NIST call for proposals (matching or exceeding the brute-force security of AES-192).

Two variants of each of the above schemes are provided:

  • FrodoKEM-640-AES and FrodoKEM-976-AES, which use AES128 to pseudorandomly generate a large public matrix (called A).
  • FrodoKEM-640-cSHAKE and FrodoKEM-976-cSHAKE, which use cSHAKE128 to pseudorandomly generate the matrix.

The AES variants are particularly suitable for devices having AES hardware acceleration (such as AES-NI on Intel platforms), while the cSHAKE variants generally provide competitive or better performance in comparison with the AES variants in the absence of hardware acceleration.

Keywords: post-quantum cryptography, key exchange, learning with errors


Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, Douglas Stebila. FrodoKEM: Learning with errors key encapsulation. Submission to the NIST Post-Quantum Cryptography standardization project. November 2017. © The authors.