C11 FIPS 203 IPD

For fun and also to provide feedback during the draft phase, I created a C11 implementation of the FIPS 203 initial public draft (IPD).

FIPS 203 is a slightly modified version of Kyber, and will (eventually) become NIST’s standarized post-quantum key encapsulation mechanism (KEM).

Features

Full implementation of all three parameter sets from the FIPS 203 initial public draft.
C11, no external dependencies (other than the standard library).
Constant-time Barrett reduction. Not vulnerable to KyberSlash.
Test suite w/ common sanitizers enabled (make test).
Doxygen-friendly API documentation (fips203ipd.h). Also available online here.
Short example application (examples/0-hello-kem/).
Independent implementation. Not based on other libraries.

Git Repository, API Documentation

Note: This is an initial release based on the draft standard with no real optimization; it is probably slower than other implementations.

Another Note: Worth reading before relying on any Kyber implementation: 2020.10.03: The inability to count correctly, by Dan Bernstein (djb).

Example

Below is the source code and output of a minimal C11 example application which demonstrates the following:

Alice generates a random KEM512 encapsulation/decapsulation key pair.
Alice sends the encapsulation key to Bob.
Bob uses the encapsulation key sent by Alice to encapsulate a random shared secret as ciphertext.
Bob sends the ciphertext to Alice.
Alice uses the decapsulation key to decapsulate the shared secret from the ciphertext sent by Bob.
Application verifies that the shared secrets from steps #3 and #5 match.

This example is also included in the git repository as examples/0-hello-kem/.

Example Source Code

//
// hello.c: minimal example of a two parties "alice" and "bob"
// generating a shared secret with KEM512.
//
// Build by typing `make` and run by typing `./hello`.
//

#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 decapsultion 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: example only; memcmp() is 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;
  }
}

Example Output

Output of ./hello with longer lines truncated for brevity:

> ./hello
alice: keygen random (64 bytes) = d656012a9eb09aa50e77a205188f0156e98276a584dcc11c2dfef0c06003ca38b233fab93e9f8dd5adec32278c8d091190112285b7389510bd610ec7b23376b2
alice: generated encapsulation key `ek` and decapsulation key `dk`:
alice: ek (800 bytes) = af3b0497f6 ... (omitted) ... 31f0f62cbd
alice: dk (1632 bytes) = e598a49eb0 ... (omitted) ... c06003ca38
alice: sending encapsulation key `ek` to bob

bob: encaps random (32 bytes) = 0db6c39742ba8cb8d9a1c437d62fed4c7fa04e944a47a73a94426dd3c33e6213
bob: generated secret `b_key` and ciphertext `ct`:
bob: b_key (32 bytes) = 32c9eb490db7e8500d9b209d78a9367fd73a967d8d58edff8655273c8d4ce8d5
bob: ct (768 bytes) = bd39ae1157 ... (omitted) ... 9b5751fc34
bob: sending ciphertext `ct` to alice

alice: used `dk` to decapsulate secret from `ct` into `a_key`:
alice: a_key (32 bytes) = 32c9eb490db7e8500d9b209d78a9367fd73a967d8d58edff8655273c8d4ce8d5

SUCCESS! alice secret `a_key` and bob secret `b_key` match.

Update (2023-10-10): Fixed typos, added rationale to intro, and added a brief explanation to the example section.

Update (2023-10-19): Released v0.2 with documentation improvements, speed improvements, a new example, and online API documentation.

Update (2024-02-14): Added Barrett reduction and independent implementation to feature list. Minor wording fixes.

Update (2024-03-04): Released v0.3. Added AVX-512 polynomial arithmetic, speed improvements, the NIST draft ML-KEM test vectors, and documentation updates.

Update (2024-04-08): Released v0.4. Added AVX-512 NTT and inverse NTT, add “Benchmarks” and “AVX-512 Backend” sections to README.md.

Update (2024-04-28): Released v0.5. Much faster (AVX-512: ~27% reduction in median CPU cycles, scalar: ~13% reduction in median CPU cycles), code cleanup, internal documentation improvements.

Update (2024-05-15): Released v0.6. Added Neon backend, backend auto-detection, test suite MacOS support, Raspberry Pi 5 benchmarks, documentation improvements.

C11 FIPS 203 IPD

October 7, 2023

Features

Example

Example Source Code

Example Output