FrodoKEM: Learning with Errors Key Encapsulation

This C library implements FrodoKEM, an IND-CCA secure key encapsulation (KEM) protocol based on the well-studied Learning with Errors (LWE) problem [1,3], which in turn has close connections to conjectured-hard problems on generic, "algebraically unstructured" lattices. This package also includes Python reference implementations. FrodoKEM is conjectured to be secure against quantum computer attacks.

FrodoKEM consists of two main variants:

• A standard variant (simply called FrodoKEM) that does not impose any restriction on the reuse of key pairs (i.e., it is suitable for applications in which a large number of ciphertexts may be encrypted to a single public key), and
• An ephemeral variant (called eFrodoKEM) that is suitable for applications in which not many ciphertexts are encrypted to a single public-key.

In contrast to eFrodoKEM, standard FrodoKEM uses an enlarged seed for generating the seed for sampling the secret and error matrices, and includes an additional salt in one of the hashing computations in encapsulation and decapsulation. These countermeasures safeguard standard FrodoKEM against some multi-ciphertext attacks. Refer to [3] for more details on these two variants.

Concretely, this library includes the following KEM schemes using AES128 for the generation of the public matrix "A":

• FrodoKEM-640-AES and eFrodoKEM-640-AES: matching the post-quantum security of AES128.
• FrodoKEM-976-AES and eFrodoKEM-976-AES: matching the post-quantum security of AES192.
• FrodoKEM-1344-AES and eFrodoKEM-1344-AES: matching the post-quantum security of AES256.

And the following KEM schemes using SHAKE128 for the generation of the public matrix "A":

• FrodoKEM-640-SHAKE and eFrodoKEM-640-SHAKE: matching the post-quantum security of AES128.
• FrodoKEM-976-SHAKE and eFrodoKEM-976-SHAKE: matching the post-quantum security of AES192.
• FrodoKEM-1344-SHAKE and eFrodoKEM-1344-SHAKE: matching the post-quantum security of AES256.

The label "eFrodoKEM" corresponds to the ephemeral variants.

The library was developed by the FrodoKEM team and Microsoft Research for experimentation purposes.

Contents

• common folder: random functions, implementations of AES and SHA-3.
• eFrodoKEM folder: C and Python3 implementations of eFrodoKEM.
• estimates folder: cryptanalysis estimates of FrodoKEM reported in [3].
• FrodoKEM folder: C and Python3 implementations of standard FrodoKEM.
• LICENSE: MIT license file.
• README.md: this readme file.

Supported Platforms

The FrodoKEM library is supported on a wide range of platforms including x64, x86, ARM, PowerPC and s390x processors running Windows, Linux or macOS, and supports both little-endian and big-endian formats. We have tested the library with Microsoft Visual Studio, GNU GCC, and clang.

License

This software is licensed under the MIT License; see the LICENSE file for details. The Python3 implementation is licensed under the Creative Commons Zero v1.0 Universal license. It includes some third party modules that are licensed differently. In particular:

• common/aes/aes_c.c: public domain
• common/aes/aes_ni.c: public domain
• common/sha3/fips202.c: public domain
• common/sha3/fips202x4.c: public domain
• common/sha3/keccak4x: all files in this folder are public domain (CC0), excepting
• common/sha3/keccak4x/brg_endian.h which is copyrighted by Brian Gladman and comes with a BSD 3-clause license.
• <FrodoKEM_variant>/tests/ds_benchmark.h: public domain
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>.c: copyrighted by Lawrence E. Bassham
• <FrodoKEM_variant>/tests/PQCtestKAT_kem<#>_shake.c: copyrighted by Lawrence E. Bassham
• <FrodoKEM_variant>/tests/rng.c: copyrighted by Lawrence E. Bassham

References

[1] Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila, "FrodoKEM: Learning With Errors Key Encapsulation". Submission to the NIST Post-Quantum Standardization project, 2021-2023. The round 3 specification of FrodoKEM is available here.

[2] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila, "Frodo: Take off the ring! Practical, quantum-secure key exchange from LWE". ACM CCS 2016, 2016. The preprint version is available here.

[3] Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, and Fernando Virdia, "FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism". IACR Communications in Cryptology (to appear), 2025.

Contributing

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.