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], which in turn has close connections to conjectured-hard problems on generic, "algebraically unstructured" lattices.
FrodoKEM is conjectured to be secure against quantum computer attacks.

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

• FrodoKEM-640-AES: matching the post-quantum security of AES128.
• FrodoKEM-976-AES: matching the post-quantum security of AES192.
• FrodoKEM-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: matching the post-quantum security of AES128.
• FrodoKEM-976-SHAKE: matching the post-quantum security of AES192.
• FrodoKEM-1344-SHAKE: matching the post-quantum security of AES256.

The library was developed by Microsoft Research for experimentation purposes.

Contents

• KAT folder: Known Answer Test (KAT) files for the KEM.
• src folder: C and header files. Public APIs can be found in api_frodo640.h, api_frodo976.h and api_frodo1344.h.
• Optimized matrix operations: optimized implementation of the matrix operations.
• Reference matrix operations: reference implementation of the matrix operations.
• AES folder: AES implementation.
• random folder: randombytes function using the system random number generator.
• sha3 folder: SHA-3 / SHAKE128 / SHAKE256 implementation.
• Test folder: test files.
• Visual Studio folder: Visual Studio 2015 files for compilation in Windows.
• Makefile: Makefile for compilation using the GNU GCC or clang compilers on Unix-like operative systems.
• License: MIT license file.
• Readme: this readme file.

Complementary crypto functions

Random values are generated with /dev/urandom on Unix-like operative systems, and CNG's BCryptGenRandom function in Windows.
Check the folder random for details.

The library includes standalone implementations of AES and SHAKE. The generation of the matrix
"A" (see the specification document [1]) can be carried out with either AES128 or SHAKE128. By
default AES128 is used.

There are two options for AES: the standalone implementation that is included in the software or
OpenSSL's AES implementation. OpenSSL's AES implementation is used by default.

Supported Platforms

The FrodoKEM library is supported on a wide range of platforms including x64, x86, ARM and PowerPC devices running Windows, Linux or macOS,
and supports both little-endian and big-endian formats.
We have tested the library with Microsoft Visual Studio 2015, GNU GCC v7.2, and clang v3.8.
See instructions below to choose an implementation option and compile on one of the supported platforms.

Implementation Options

The following implementation options are available:

• Reference portable implementation enabled by setting OPT_LEVEL=REFERENCE.
• Optimized portable implementation enabled by setting OPT_LEVEL=FAST_GENERIC.
• Optimized x64 implementation using AVX2 intrinsics and AES-NI instructions enabled by setting ARCH=x64 and OPT_LEVEL=FAST.

Follow the instructions in the sections "Instructions for Linux" or "Instructions for Windows" below to configure these different implementation options.

Instructions for Linux

Using AES128

By simply executing:

$ make

the library is compiled for x64 using gcc, and optimization level FAST, which uses AVX2 instrinsics.
AES128 is used by default to generate the matrix "A". For AES, OpenSSL's AES implementation is used by default.

Testing and benchmarking results are obtained by running:

$ ./frodo640/test_KEM
$ ./frodo976/test_KEM
$ ./frodo1344/test_KEM

To run the implementations against the KATs, execute:

$ ./frodo640/PQCtestKAT_kem
$ ./frodo976/PQCtestKAT_kem
$ ./frodo1344/PQCtestKAT_kem

Using SHAKE128

By executing:

$ make GENERATION_A=SHAKE128

the library is compiled for x64 using gcc, and optimization level FAST, which uses AVX2 instrinsics.
SHAKE128 is used to generate the matrix "A".

Testing and benchmarking results are obtained by running:

$ ./frodo640/test_KEM
$ ./frodo976/test_KEM
$ ./frodo1344/test_KEM

To run the implementations against the KATs, execute:

$ ./frodo640/PQCtestKAT_kem_shake
$ ./frodo976/PQCtestKAT_kem_shake
$ ./frodo1344/PQCtestKAT_kem_shake

Additional options

These are all the available options for compilation:

$ make CC=[gcc/clang] ARCH=[x64/x86/ARM] OPT_LEVEL=[REFERENCE/FAST_GENERIC/FAST] GENERATION_A=[AES128/SHAKE128] USE_OPENSSL=[TRUE/FALSE]

Note that the FAST option is only available for x64 with support for AVX2 and AES-NI instructions.
The USE_OPENSSL flag specifies whether OpenSSL's AES implementation is used (=TRUE) or if the
standalone AES implementation is used (=FALSE). Therefore, this flag only applies when GENERATION_A= AES128 (or if GENERATION_A is left blank).

If OpenSSL is being used and is installed in an alternate location, use the following make options:

OPENSSL_INCLUDE_DIR=/path/to/openssl/include
OPENSSL_LIB_DIR=/path/to/openssl/lib

The program tries its best at auto-correcting unsupported configurations.
For example, since the FAST implementation is currently only available for x64 doing make ARCH=x86 OPT_LEVEL=FAST
is actually processed using ARCH=x86 OPT_LEVEL=FAST_GENERIC.

Instructions for Windows

Building the library with Visual Studio:

Open the solution file frodoKEM.sln in Visual Studio, and choose either x64 or x86 from the platform menu.
Make sure Fast_generic is selected in the configuration menu. Finally, select "Build Solution" from the "Build" menu.

Running the tests:

After building the solution file, there should be three executable files: test_KEM640.exe, test_KEM976.exe and test_KEM1344.exe, to run tests for the KEM.

Using the library:

After building the solution file, add the generated FrodoKEM-640.lib, FrodoKEM-976.lib and FrodoKEM-1344.lib library files to the set of References for a project,
and add api_frodo640.h, api_frodo976.h and api_frodo1344.h to the list of header files of a project.

License

This software is licensed under the MIT License; see the LICENSE file for details.
It includes some third party modules that are licensed differently. In particular:

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

Contributors

The library was developed by Microsoft Research using as basis the Frodo implementation from liboqs,
which in turn is based on [2].

Other contributors include:

• Erdem Alkim, while he was an intern with Microsoft Research.
• Douglas Stebila.

References

[1] Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila,
"FrodoKEM: Learning With Errors Key Encapsulation". Submission to the NIST Post-Quantum Standardization project, 2017-2019. The round 2 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.

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.