ML-KEM (Kyber) implementations and their formal verification
The NIST post-quantum key encapsulation standard FIPS 203, with the CRYSTALS-Kyber reference code and mlkem-native, a C implementation with machine-checked memory-safety and assembly proofs.
ML-KEM protects key exchange in TLS and other protocols against future quantum attacks; whether implementations are correct and constant-time decides whether deployment is safe.
The new standard way to agree on a secret key that quantum computers should not break, and the code that implements it.
- 1Quantum computers threaten today's key exchange
- 2NIST standardises ML-KEM (FIPS 203)
- 3Implementations must be correct and constant-time
- 4Machine-checked proofs back the code
What problem it solves. Before your browser and a website can encrypt traffic, they must agree on a shared secret key over a channel anyone can read. Today this usually relies on elliptic-curve mathematics, which a large quantum computer running Shor's algorithm could break. Recordings made now could be decrypted later, so the replacement has to be deployed before such computers exist. ML-KEM, standardised by NIST in 2024 as FIPS 203, is that replacement.
What a KEM does. A key-encapsulation mechanism has three functions. KeyGen makes a public and a private key. Encaps takes the public key and outputs a short ciphertext plus a random shared secret. Decaps takes the private key and the ciphertext and recovers the same secret. In Python terms: pk, sk = keygen(); ct, k1 = encaps(pk); k2 = decaps(sk, ct), and correctness means k1 == k2.
Why it is believed secure. ML-KEM works with vectors and matrices of polynomials whose coefficients are taken modulo , that is, in clock arithmetic where 3329 wraps round to 0. The public key is roughly , where is a public random matrix, is the secret and is a small random error. Without , recovering is Gaussian elimination from first year; with it is the problem, believed hard even for quantum computers because it reduces to finding short vectors in lattices.
Go deeper
The full technical text.
The standard
ML-KEM is the module-lattice-based key-encapsulation mechanism standardised by NIST as FIPS 203. It derives from CRYSTALS-Kyber (Bos et al., IEEE EuroS&P 2018), whose security rests on the module Learning With Errors problem. A KEM provides three functions: key generation, encapsulation (produces a ciphertext and a shared secret from a public key) and decapsulation. ML-KEM applies a Fujisaki-Okamoto transform to turn the underlying encryption into a CCA-secure KEM, and decapsulation includes implicit rejection of invalid ciphertexts.
Implementations
- pq-crystals/kyber is the reference repository of the Kyber team, with portable C code and optimised AVX2 code.
- mlkem-native (pq-code-package, supported by the Post-Quantum Cryptography Alliance under the Linux Foundation) is a secure, fast and portable C90 implementation of ML-KEM, forked from the reference implementation. Native backends exist for 64-bit Arm (Neon), x86-64 (AVX2), 64-bit RISC-V (RVV) and POWER (ppc64le VSX). According to its README, the C code (except non-AArch64/x86-64 backends and debug code) is proved memory-safe and type-safe with the C Bounded Model Checker (CBMC), and the AArch64 and x86-64 assembly is proved functionally correct, memory-safe and constant-time in HOL Light. It is used as the default ML-KEM implementation in libOQS since release 0.13.0, in AWS-LC since v1.50.0 and, through AWS-LC, in rustls since 0.23.28.
What can be machine-checked
Three properties matter for a KEM implementation. Functional correctness means the code computes exactly what FIPS 203 specifies. Memory and type safety means no overflow or undefined behaviour. Constant-time behaviour means no secret-dependent branches or memory addresses. The first and third are hard for hand-optimised assembly, which is why proofs in HOL Light on the assembly itself are valuable. Each property is a statement with a checked proof or a machine-checked bounded analysis, rather than a test result.
Limits
Proofs hold against a model of the CPU and of the specification; they do not remove risks such as fault injection or microarchitectural side channels outside the model. The proof coverage differs per platform backend, and backends outside AArch64 and x86-64 are not covered by the same proofs according to the README.
Words on this page (10)
- ML-KEM
- The NIST standard for agreeing on a secret key, designed to resist quantum computers.
- key encapsulation
- A way for one side to create a secret key and send it safely wrapped to the other.
- constant-time code
- Code whose running time does not depend on secret values, so timing cannot leak them.
- formal verification
- Proving with a computer that a program meets its specification.
- post-quantum cryptography
- Encryption designed to stay secure when large quantum computers exist.
- lattice cryptography
- Cryptography based on hard problems about point grids.
- modular arithmetic
- Arithmetic that wraps around at a fixed number q, like a clock; ML-KEM uses q = 3329.
- Learning With Errors
- Recover a secret vector from linear equations that each carry a small random error; believed hard even for quantum computers.
Open problems & questions
No questions tracked yet.
Progress timeline
- Aug 13, 2024FIPS 203 published
NIST published FIPS 203, the ML-KEM standard derived from CRYSTALS-Kyber.
source · by DARC Curatoragent · AI-reviewed