Embeddable, dependency-free C11 implementation of ML-KEM from the FIPS 203 initial public draft (IPD) with scalar and AVX-512 backends.

FIPS 203 is (or will be) NIST's standardized version of Kyber, a post-quantum key encapsulation mechanism (KEM).

Notes on this implementation:

Uses constant-time Barrett reduction. Not vulnerable to KyberSlash.
Compile-time AVX-512-accelerated backend.
Coefficients are reduced modulo Q during polynomial deserialization, as per this discussion.
Test suite is built-in to fips203ipd.c (see bottom of file) and compiles with common sanitizers enabled.
Includes (and passes) test vectors from the NIST PQC Intermediate Values for Draft ML-KEM.
Full Doxygen API documentation. Available online here.
Randomness for keygen() and encaps() is specified as a function parameter.
Uses my SHA-3 implementation internally.

Use make to build a minimal self test application, make doc to build the HTML-formatted API documentation, and make test to run the test suite.

Example

Minimal example of Alice and Bob exchanging a shared secret with KEM512:

//
// hello.c: minimal example of a two parties "alice" and "bob"
// generating a shared secret with KEM512.
//
#include <stdio.h> // fputs()
#include <string.h> // memcmp()
#include "hex.h" // hex_write()
#include "rand-bytes.h" // rand_bytes()
#include "fips203ipd.h" // fips203ipd_*()
 
int main(void) {
  //
  // alice: generate keypair
  //
  uint8_t ek[FIPS203IPD_KEM512_EK_SIZE] = { 0 }; // encapsulation key
  uint8_t dk[FIPS203IPD_KEM512_DK_SIZE] = { 0 }; // decapsulation key
  {
    // alice: get 64 random bytes for keygen()
    uint8_t keygen_seed[64] = { 0 };
    rand_bytes(keygen_seed, sizeof(keygen_seed));
 
    fputs("alice: keygen random (64 bytes) = ", stdout);
    hex_write(stdout, keygen_seed, sizeof(keygen_seed));
    fputs("\n", stdout);
 
    // alice: generate encapsulation/decapsulation key pair
    fips203ipd_kem512_keygen(ek, dk, keygen_seed);
  }
  fputs("alice: generated encapsulation key `ek` and decapsulation key `dk`:\n", stdout);
  printf("alice: ek (%d bytes) = ", FIPS203IPD_KEM512_EK_SIZE);
  hex_write(stdout, ek, sizeof(ek));
  printf("\nalice: dk (%d bytes) = ", FIPS203IPD_KEM512_DK_SIZE);
  hex_write(stdout, dk, sizeof(dk));
  fputs("\n", stdout);
 
  // alice send `ek` to bob
  fputs("alice: sending encapsulation key `ek` to bob\n\n", stdout);
 
  //
  // bob: generate shared secret and ciphertext
  //
  uint8_t b_key[32] = { 0 }; // shared secret
  uint8_t ct[FIPS203IPD_KEM512_CT_SIZE] = { 0 }; // ciphertext
  {
    // bob: get 32 random bytes for encaps()
    uint8_t encaps_seed[32] = { 0 };
    rand_bytes(encaps_seed, sizeof(encaps_seed));
 
    fputs("bob: encaps random (32 bytes) = ", stdout);
    hex_write(stdout, encaps_seed, sizeof(encaps_seed));
    fputs("\n", stdout);
 
    // bob:
    // 1. get encapsulation key `ek` from alice.
    // 2. generate random shared secret.
    // 3. use `ek` from step #1 to encapsulate the shared secret from step #2.
    // 3. store the shared secret in `b_key`.
    // 4. store the encapsulated shared secret (ciphertext) in `ct`.
    fips203ipd_kem512_encaps(b_key, ct, ek, encaps_seed);
  }
 
  fputs("bob: generated secret `b_key` and ciphertext `ct`:\nbob: b_key (32 bytes) = ", stdout);
  hex_write(stdout, b_key, sizeof(b_key));
  printf("\nbob: ct (%d bytes) = ", FIPS203IPD_KEM512_CT_SIZE);
  hex_write(stdout, ct, sizeof(ct));
  fputs("\n", stdout);
 
  // bob sends ciphertext `ct` to alice
  fputs("bob: sending ciphertext `ct` to alice\n\n", stdout);
 
  //
  // alice: decapsulate shared secret
  //
 
  // alice:
  // 1. get ciphertext `ct` from bob.
  // 2. use decapsulation key `dk` to decapsulate shared secret from `ct`.
  // 2. store shared secret in `a_key`.
  uint8_t a_key[32] = { 0 };
  fips203ipd_kem512_decaps(a_key, ct, dk);
 
  fputs("alice: used `dk` to decapsulate secret from `ct` into `a_key`:\nalice: a_key (32 bytes) = ", stdout);
  hex_write(stdout, a_key, sizeof(a_key));
  fputs("\n\n", stdout);
 
  // check result
  // (note: don't use memcmp() in real applications; it's not constant-time)
  if (!memcmp(a_key, b_key, sizeof(a_key))) {
    // success: alice and bob have the same shared secret
    fputs("SUCCESS! alice secret `a_key` and bob secret `b_key` match.\n", stdout);
    return 0;
  } else {
    // failure: alice and bob do not have the same shared secret
    fputs("FAILURE! alice secret `a_key` and bob secret `b_key` do not match.\n", stdout);
    return -1;
  }
}

See examples/0-hello-kem/ for the full buildable example, including a Makefile and support files.

Documentation

API documentation is available online here and also in fips203ipd.h. If you have Doxygen installed, you can build HTML-formatted API documentation by typing make doc.

Tests

Use make test to build and run the test suite.

The test suite checks each component of this implementation for expected answers and is built with common sanitizers supported by both GCC and Clang. The source code for the test suite is embedded at the bottom of fips203ipd.c behind a TEST_FIPS203IPD define.

You can also build a quick test application by typing make in the top-level directory. The test application does the following 1000 times for each parameter set:

Generate a random encapsulation/decapsulation key pair.
Encapsulate a secret using the encapsulation key.
Decapsulate the secret using the decapsulation key.
Verify that the secrets generated in steps #2 and #3 match.

Usage

There are safer and faster alternatives, but if you want to use this library anyway:

Copy fips203ipd.h and fips203ipd.c into your source tree.
Update your build system to compile fips203ipd.o.
Include fips203ipd.h in your application.
Use fips203ipd_*() functions in your code.

Benchmarks

A minimal libcpucycles-based benchmarking tool is available in examples/3-bench/. The bench tool repeatedly measures the number of CPU cycles used for the key generation, encapsulation, and decapsulation functions for each parameter set and then prints summary statistics to standard output in CSV format.

The results from running bench on a couple of my systems are available in the tables below.

Lenovo ThinkPad X1 Carbon, 6th Gen (x86-64, i7-1185G7, AVX-512 backend)

set	function	median	mean	stddev	min	max
kem512	keygen	26213	26366	829	25787	77486
kem512	encaps	27783	27950	933	27359	98549
kem512	decaps	36595	36805	1260	36025	106029
kem768	keygen	42545	42686	840	41834	141156
kem768	encaps	42037	42179	799	41413	99132
kem768	decaps	54145	54237	972	53241	104424
kem1024	keygen	57576	57828	1156	56668	129521
kem1024	encaps	58111	58368	1205	57193	122737
kem1024	decaps	73894	74139	1410	72419	135592

Odroid N2L (ARM64, Cortex-A73, scalar backend)

set	function	median	mean	stddev	min	max
kem512	keygen	246960	247080	764	245026	261638
kem512	encaps	253445	253570	738	251716	268071
kem512	decaps	356719	356873	800	355008	376107
kem768	keygen	381157	381370	1128	378007	400920
kem768	encaps	386998	387212	1106	384123	402892
kem768	decaps	529516	529751	1200	526635	555099
kem1024	keygen	552952	553232	1510	549059	574011
kem1024	encaps	550178	550473	1514	546348	570717
kem1024	decaps	733125	733417	1615	728842	757292

AVX-512 Backend

This library includes a compile-time AVX-512 backend, implemented via intrinsics. When the AVX-512 backend is enabled, the following functions are replaced with AVX-512-accelerated equivalents:

Functions	Description
`permute()`	block permutation for SHA3-256 and SHA3-512
`poly_{ntt,inv_ntt}()`	Number-Theoretic Transform (NTT) and inverse NTT
`poly_{add,sub,mul}()`	Polynomial arithmetic
`poly_encode()`, `poly_encode_{11,10,5,4,1}bit()`	Polynomial encoding
`pke{512,768,1024}_keygen_avx512()`	Key generation (see below)
`pke{512,768,1024}_encrypt_avx512()`	Encryption (see below)

The AVX-512-enabled key generation and encryption functions perform coefficient sampling in stages and use the 64-bit lanes of 25 512-bit registers to permute and sample from up to 8 SHAKE128 and SHAKE256 contexts at once.

Here are how the lanes of the AVX-512 registers are used for each parameter set, function, and stage:

Parameter Set	Function	Stage	Lane 0	Lane 1	Lane 2	Lane 3	Lane 4	Lane 5	Lane 6	Lane 7
KEM512	keygen	1	A[0,0]	A[0,1]	A[1,0]	A[1,1]	s[0]	s[1]	e[0]	e[1]
KEM512	encrypt	1	A[0,0]	A[1,0]	A[0,1]	A[1,1]	r[0]	r[1]	n/a	n/a
KEM512	encrypt	2	e1[0]	e1[1]	e2	n/a	n/a	n/a	n/a	n/a
KEM768	keygen	1	A[0,0]	A[0,1]	A[0,2]	A[1,0]	A[1,1]	A[1,2]	A[2,0]	A[2,1]
KEM768	keygen	2	A[2,2]	s[0]	s[1]	s[2]	e[0]	e[1]	e[2]	n/a
KEM768	encrypt	1	A[0,0]	A[1,0]	A[2,0]	A[0,1]	A[1,1]	A[2,1]	A[0,2]	A[1,2]
KEM768	encrypt	2	A[2,2]	r[0]	r[1]	r[2]	e1[0]	e1[1]	e1[2]	e2
KEM1024	keygen	1	A[0,0]	A[0,1]	A[0,2]	A[0,3]	A[1,0]	A[1,1]	A[1,2]	A[1,3]
KEM1024	keygen	2	A[2,0]	A[2,1]	A[2,2]	A[2,3]	A[3,0]	A[3,1]	A[3,2]	A[3,3]
KEM1024	keygen	3	s[0]	s[1]	s[2]	s[3]	e[0]	e[1]	e[2]	e[3]
KEM1024	encrypt	1	A[0,0]	A[1,0]	A[2,0]	A[3,0]	A[0,1]	A[1,1]	A[2,1]	A[3,1]
KEM1024	encrypt	2	A[0,2]	A[1,2]	A[2,2]	A[3,2]	A[0,3]	A[1,3]	A[2,3]	A[3,3]
KEM1024	encrypt	3	r[0]	r[1]	r[2]	r[3]	e1[0]	e1[1]	e1[2]	e1[3]
KEM1024	encrypt	4	e2	n/a	n/a	n/a	n/a	n/a	n/a	n/a

References

License

MIT No Attribution (MIT-0)

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.