About FrodoKEM

FrodoKEM is a family of key-encapsulation mechanisms that 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),
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 AES-128 to pseudorandomly generate a large public matrix (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.

FrodoKEM has been selected as a "Round 3 alternate candidate" in the NIST Post-Quantum Cryptography Standardization project.

FrodoKEM, at level 3 and 5, is one of two post-quantum algorithms recommended by the German Federal Office for Information Security (BSI) as cryptographically suitable for long-term confidentiality.

Team

The inventors of FrodoKEM are:

Erdem Alkim
Joppe W. Bos, NXP Semiconductors
Léo Ducas, CWI
Patrick Longa, Microsoft Research
Ilya Mironov
Michael Naehrig, Microsoft Research
Valeria Nikolaenko
Chris Peikert, University of Michigan
Ananth Raghunathan
Douglas Stebila, University of Waterloo

Additional submitters for the FrodoKEM NIST submission are:

Karen Easterbrook, Microsoft Research
Brian LaMacchia, Microsoft Research

FrodoKEM builds on an extensive line of literature which is detailed in the specification.

You can contact the FrodoKEM team by emailing contact@frodokem.org.

Specification

The current version of the FrodoKEM specification is the NIST Round 3 submission, June 4 2021 update:

View FrodoKEM specification (PDF)

Code

Our submission package includes:

a reference implementation written exclusively in portable C,
an optimized implementation written exclusively in portable C that includes efficient algorithms to generate the matrix A and to compute the matrix operations AS + E and S'A + E',
an additional, optimized implementation for x64 platforms that exploits Advanced Vector Extensions 2 (AVX2) intrinsic instructions, and
a extensively commented reference implementation written exclusively in Python 3.

The implementations in the submission package support all six schemes: FrodoKEM-640-AES, FrodoKEM-640-SHAKE, FrodoKEM-976-AES, FrodoKEM-976-SHAKE, FrodoKEM-1344-AES, and FrodoKEM-1344-SHAKE. The only difference between the reference and the optimized implementation is that the latter includes two efficient functions to generate the public matrix A and to compute the matrix operations AS + E and S'A + E'. Similarly, the only difference between the optimized and the additional implementation is that the latter uses AVX2 intrinsic instructions to speed up the implementation of the aforementioned functions. Hence, the different implementations share most of their codebase: this illustrates the simplicity of software based on FrodoKEM.

All our implementations avoid the use of secret address accesses and secret branches and, hence, are protected against timing and cache attacks.

Our GitHub project contains a version of our submission package code that is more amenable to building as a standalone library:

View FrodoKEM code on GitHub

Downloads

June 4, 2021 update

FrodoKEM Round 3 specification – 2021/06/04 (PDF)

NIST Round 3 submission (September 30, 2020)

March 25, 2020 update

July 2, 2019 update

NIST Round 2 submission (March 30, 2019)

NIST Round 1 submission (November 30, 2017)

Pre-NIST

"Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE" In Proc. 23rd ACM Conference on Computer and Communications Security (CCS) 2016 (PDF)

Third-party implementations

FrodoKEM in Go, by Eduardo Riccardi
FrodoKEM in Go via Cloudflare's CIRCL library, by Goutam Tamvada

News

December 16, 2019: Tagesspiegel Background: "Informationssicherheit im Quantenzeitalter" – Arne Schönbohm, President of the Bundesamt für Sicherheit in der Informationstechnik (BSI), announces that FrodoKEM will be recommended by BSI as one of two key exchange methods that are 'fundamentally suitable (in hybrid solutions)'.
July 22, 2020: NIST Round 3 Candidates – FrodoKEM is selected by NIST as a Round 3 "alternate candidate".
August 24, 2020: Post-Quanten-Kryptografie: Update der Handlungsempfehlungen – Germany's Bundesamt für Sicherheit in der Informationstechnik (BSI) continues to recommend FrodoKEM for providing post-quantum confidentiality.
March 31, 2021: BSI TR-02102-1 "Cryptographic Procedures: Recommendations and Key Lengths" Version: 2021-01: BSI recommendation for use of FrodoKEM for post-quantum confidentiality.
January 18, 2022: Prepare for the threat of quantumcomputers – The Netherlands National Communications Security Agency (NLNCSA) recommends FrodoKEM to achieve post-quantum confidentiality.

FrodoKEM

Practical quantum-secure key encapsulation from generic lattices