Home

Awesome

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:

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":

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

The label "eFrodoKEM" corresponds to the ephemeral variants.

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

Contents

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:

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] FrodoKEM team, "FrodoKEM: Learning With Errors Key Encapsulation - Preliminary Draft Standards". Submission to ISO/IEC JTC1/SC27/WG2, 2023. The preliminary draft is available here.

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.