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 consists of two variants determined on whether there is key reuse: a standard variant that does not impose any restriction on the reuse of key pairs, and an ephemeral variant (eFrodoKEM) that generates a fresh key pair per instantiation of the protocol.
For each security level and variant, there is a choice of the symmetric primitive used in one step of the protocol:
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 was selected as a "Round 3 alternate candidate" in the NIST Post-Quantum Cryptography Standardization project, but was not selected for standardization.
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.
The inventors of FrodoKEM are:
Additional submitters for the FrodoKEM NIST submission are:
FrodoKEM builds on an extensive line of literature which is detailed in the specification.
You can contact the FrodoKEM team by emailing firstname.lastname@example.org.
The current version of the FrodoKEM specification is the Preliminary Standardization Proposal submitted to ISO (2023/03/14):
This document is complemented by Annex on FrodoKEM updates, April 18, 2023 version (PDF) and the NIST Round 3 specification, June 2021 update.
We make available:
The implementations support all twelve schemes: FrodoKEM-640-AES, FrodoKEM-640-SHAKE, FrodoKEM-976-AES, FrodoKEM-976-SHAKE, FrodoKEM-1344-AES, and FrodoKEM-1344-SHAKE, and eFrodoKEM-640-AES, eFrodoKEM-640-SHAKE, eFrodoKEM-976-AES, eFrodoKEM-976-SHAKE, eFrodoKEM-1344-AES, and eFrodoKEM-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.
Preliminary Standardization Proposal (March/April, 2023)
June 4, 2021 update
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)
Copyright © FrodoKEM team 2017–2023.
FrodoKEM source code licensed under MIT License; see GitHub project for details.
Cover image by LoveToTakePhotos on pixabay.com.