fips203ipd
C11 implementation of FIPS 203 initial public draft (IPD).
fips203ipd

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:

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;
}
}
C11 implementation of ML-KEM from the FIPS 203 initial public draft.
#define FIPS203IPD_KEM512_DK_SIZE
Size of KEM512 decapsulation key, in bytes (768 * K + 96).
Definition: fips203ipd.h:79
#define FIPS203IPD_KEM512_CT_SIZE
Size of KEM512 ciphertext, in bytes (32 * (DU * K + DV)).
Definition: fips203ipd.h:85
#define FIPS203IPD_KEM512_EK_SIZE
Size of KEM512 encapsulation key, in bytes (384 * K + 32).
Definition: fips203ipd.h:73
void fips203ipd_kem512_keygen(uint8_t ek[static FIPS203IPD_KEM512_EK_SIZE], uint8_t dk[static FIPS203IPD_KEM512_DK_SIZE], const uint8_t seed[static FIPS203IPD_KEYGEN_SEED_SIZE])
Generate KEM512 encapsulation key ek and decapsulation key dk from 64 byte random seed seed.
void fips203ipd_kem512_encaps(uint8_t key[static FIPS203IPD_KEY_SIZE], uint8_t ct[static FIPS203IPD_KEM512_CT_SIZE], const uint8_t ek[static FIPS203IPD_KEM512_EK_SIZE], const uint8_t seed[static FIPS203IPD_ENCAPS_SEED_SIZE])
Generate KEM512 shared key key and ciphertext ct from given encapsulation key ek and randomness seed.
void fips203ipd_kem512_decaps(uint8_t key[static FIPS203IPD_KEY_SIZE], const uint8_t ct[static FIPS203IPD_KEM512_CT_SIZE], const uint8_t dk[static FIPS203IPD_KEM512_DK_SIZE])
Decapsulate shared key key from ciphertext ct using KEM512 decapsulation key dk with implicit rejecti...

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:

  1. Generate a random encapsulation/decapsulation key pair.
  2. Encapsulate a secret using the encapsulation key.
  3. Decapsulate the secret using the decapsulation key.
  4. 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:

  1. Copy fips203ipd.h and fips203ipd.c into your source tree.
  2. Update your build system to compile fips203ipd.o.
  3. Include fips203ipd.h in your application.
  4. 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)

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.