Red Pine on Wilderness Trail

Douglas Stebila

FrodoKEM: Learning with errors key encapsulation

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

Abstract

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 three levels:

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

Two variants of each of the above schemes are provided:

  • FrodoKEM-640-AES, FrodoKEM-976-AES, and FrodoKEM-1344-AES, which use AES128 to pseudorandomly generate a large public matrix (called A).
  • FrodoKEM-640-SHAKE, FrodoKEM-976-SHAKE, and FrodoKEM-1344-SHAKE, which use SHAKE128 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 SHAKE 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

Reference

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, Round 3. September 2020. © The authors.

Download

Code

BibTeX