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	17554	17652	789	17187	88590
kem512	encaps	21506	21615	881	21051	101018
kem512	decaps	25651	25762	755	25195	106218
kem768	keygen	29423	29634	908	28816	139110
kem768	encaps	32567	32790	886	31818	98225
kem768	decaps	38227	38419	983	37321	94642
kem1024	keygen	40003	40370	1856	39005	154322
kem1024	encaps	45420	45790	1613	44321	137191
kem1024	decaps	52720	53131	1758	51079	178304

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

set	function	median	mean	stddev	min	max
kem512	keygen	211500	212006	3036	209400	360675
kem512	encaps	217050	217589	3040	215325	355875
kem512	decaps	298650	299304	3750	296925	432225
kem768	keygen	325650	326465	4123	322575	548700
kem768	encaps	332625	333462	4202	329700	469350
kem768	decaps	445575	446704	5162	442575	587025
kem1024	keygen	476550	477710	5433	472650	620400
kem1024	encaps	476625	477805	5413	472725	598650
kem1024	decaps	620625	622082	6447	616650	769125

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,add2,sub,mul}()`	Polynomial arithmetic
`poly_encode()`, `poly_encode_{11,10,5,4,1}bit()`	Polynomial encoding
`poly_decode()`, `poly_decode_{11,10,5,4,1}bit()`	Polynomial decoding
`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.