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	17451	17706	1427	17133	69081
kem512	encaps	21505	21817	1823	21148	101224
kem512	decaps	25677	26061	2204	25301	94526
kem768	keygen	29342	29495	1262	28812	141511
kem768	encaps	32511	32648	700	31935	75814
kem768	decaps	38157	38215	719	37365	73073
kem1024	keygen	39851	40271	2762	39178	165549
kem1024	encaps	45362	45770	2035	44449	96498
kem1024	decaps	52559	53021	2513	51697	119746

Raspberry Pi 5 (ARM Cortex-A76, scalar backend)

set	function	median	mean	stddev	min	max
kem512	keygen	127136	127251	779	125757	157174
kem512	encaps	132788	132899	710	131364	141910
kem512	decaps	177466	177584	728	176220	196468
kem768	keygen	197491	197709	1023	195221	213555
kem768	encaps	205501	205721	1080	203365	233892
kem768	decaps	267134	267354	1076	264998	290274
kem1024	keygen	291386	291613	1464	288360	363520
kem1024	encaps	298462	298707	1330	295524	318887
kem1024	decaps	376559	376818	1342	373488	397563

Odroid N2L (ARM Cortex-A73, scalar backend)

set	function	median	mean	stddev	min	max
kem512	keygen	211425	211855	2149	209700	250425
kem512	encaps	216825	217304	2517	215100	286350
kem512	decaps	298275	298966	3216	296775	434325
kem768	keygen	325575	326270	2881	322950	403350
kem768	encaps	332175	332939	2776	329475	386175
kem768	decaps	445275	446286	3354	442500	517200
kem1024	keygen	476475	477483	3268	472125	538800
kem1024	encaps	476100	477106	3514	472575	597900
kem1024	decaps	620475	621714	3932	616500	694125

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.