ML-KEM

History

Peter Shor showed in 1994 that a quantum computer could factor numbers and take discrete logarithms, the problems RSA and Diffie–Hellman rest on. In 2016 NIST opened a competition for public-key algorithms that would hold against such a machine; 82 were submitted. ML-KEM, published as FIPS 203 on 13 August 2024, is derived from CRYSTALS-Kyber (Bos, Ducas, Kiltz and others, 2018). Its hardness goes back to Oded Regev’s learning with errors (2005): linear equations that are easy to solve become hard when each is slightly wrong.

How it works

A key pair is a matrix A of polynomials — 256 numbers modulo 3329 each — grown from a seed, a secret s and a noise e of small numbers: the encapsulation key is the seed and t = As + e, the decapsulation key holds s. To encrypt, the tool draws 32 random bytes m and makes a new noisy equation from the key, adding each bit of m as 0 or 1665, half of 3329. Both sides derive the 32-byte shared secret key from m; it encrypts the message with AES-256-GCM, which FIPS 203 allows a shared key to do directly. With s the receiver removes the equation’s large part and rounds 256 numbers to the nearer of 0 and 1665, as the figure shows; it re-encrypts m and compares, and a ciphertext that does not match yields an unrelated key.

How it was checked

SHA3-256, SHA3-512, SHAKE128 and SHAKE256, written here from FIPS 202, agree with Node’s OpenSSL at every block boundary. Key generation, encapsulation and decapsulation reproduced all 240 of NIST’s ACVP vectors for the three parameter sets, among them ciphertexts altered to be rejected and keys altered to fail the checks of §7.2 and §7.3; the tests keep 108 of them. Keys made by OpenSSL open messages encapsulated here, and the other way round; the transform’s constants equal the standard’s Appendix A.

Limits

JavaScript promises no constant-time arithmetic, and this is not a hardened library: it shows ML-KEM at work and carries messages between people, not traffic that must resist timing attacks. The IETF’s draft hybrids for TLS 1.3 pair ML-KEM with an elliptic-curve exchange; this tool uses ML-KEM alone. The layout of an encrypted message — ciphertext, nonce, AES-GCM — is the tool’s own, not a standard format. ML-KEM does not sign: anyone with the encapsulation key can write to it, and a message says nothing of who sent it.