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()andencaps()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.
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.
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.
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.
There are safer and faster alternatives, but if you want to use this library anyway:
- Copy
fips203ipd.handfips203ipd.cinto your source tree. - Update your build system to compile
fips203ipd.o. - Include
fips203ipd.hin your application. - Use
fips203ipd_*()functions in your code.
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.
| set | function | median | mean | stddev | min | max |
|---|---|---|---|---|---|---|
| kem512 | keygen | 17561 | 17847 | 1663 | 17215 | 93391 |
| kem512 | encaps | 21578 | 21917 | 1979 | 21126 | 117414 |
| kem512 | decaps | 25814 | 26211 | 2144 | 25309 | 110700 |
| kem768 | keygen | 29571 | 29811 | 1236 | 28908 | 117951 |
| kem768 | encaps | 33104 | 33362 | 1291 | 32450 | 132204 |
| kem768 | decaps | 38741 | 38972 | 1458 | 37822 | 135678 |
| kem1024 | keygen | 40362 | 40830 | 2226 | 39375 | 205338 |
| kem1024 | encaps | 45746 | 46249 | 2348 | 44826 | 168169 |
| kem1024 | decaps | 52947 | 53522 | 2693 | 51610 | 179749 |
| set | function | median | mean | stddev | min | max |
|---|---|---|---|---|---|---|
| kem512 | keygen | 243609 | 243724 | 749 | 241548 | 256103 |
| kem512 | encaps | 248502 | 248619 | 728 | 246585 | 260976 |
| kem512 | decaps | 350393 | 350531 | 769 | 348422 | 363378 |
| kem768 | keygen | 374669 | 374881 | 1124 | 371807 | 393553 |
| kem768 | encaps | 377614 | 377828 | 1099 | 374806 | 392127 |
| kem768 | decaps | 518455 | 518684 | 1162 | 515458 | 530758 |
| kem1024 | keygen | 542228 | 542499 | 1499 | 538026 | 562530 |
| kem1024 | encaps | 535918 | 536197 | 1490 | 531907 | 551810 |
| kem1024 | decaps | 716278 | 716555 | 1561 | 711711 | 730476 |
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 |
- FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions
- FIPS 203 (IPD): Module-Lattice-Based Key-Encapsulation Mechanism Standard
- CSRC Post-Quantum Cryptography: Intermediate Values for draft ML-KEM and draft ML-DSA
Copyright 2023-2024 Paul Duncan
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.