ML-KEM

ML-KEM is what replaces elliptic-curve Diffie–Hellman for agreeing on keys. It is fast, its keys and ciphertexts are about a kilobyte each, and its security rests on a lattice problem that no known quantum algorithm solves efficiently.

Standard
FIPS 203, August 2024, from CRYSTALS-Kyber
Rests on
Module learning with errors over Z3329[X]/(X256 + 1)
Parameter sets
ML-KEM-512, -768 and -1024, claimed at security categories 1, 3 and 5. NIST recommends ML-KEM-768 as the default
Sizes (ML-KEM-768)
1,184-byte encapsulation key, 1,088-byte ciphertext, 32-byte shared secret
Deployed as
Hybrids such as X25519MLKEM768 in TLS 1.3, which combine it with X25519

What a KEM does

A key-encapsulation mechanism has three algorithms. KeyGen makes an encapsulation key ek, which is public, and a decapsulation key dk, which is secret. Encaps(ek) produces a fresh random shared key K together with a ciphertext c. Decaps(dk, c) recovers K from c. In TLS 1.3 the client sends ek in its first message, the server replies with c, and both sides derive the session keys from K.

Unlike Diffie–Hellman, the two sides do different things, and there is no way for two parties to derive a shared key from each other's public keys alone. For a handshake that difference does not matter: one round trip carries the key share each way, exactly as with ECDH.

The hard problem

Learning with errors (LWE), introduced by Regev in 2005, asks: given a random matrix A and t = As + e, where s and e have small entries, find s. Without the error e this is linear algebra. With it, the best known methods reduce it to finding short vectors in a lattice, which is believed to be hard for classical and quantum computers alike.

ML-KEM uses the module version (MLWE). Every entry of A, s and e is a polynomial in the ring Rq = Zq[X]/(X256 + 1) with q = 3329, and A is a k × k matrix of such polynomials, with k = 2, 3 or 4. The structure makes keys small and arithmetic fast; Langlois and Stehlé showed that module lattices keep a worst-case to average-case reduction of the kind that underpins LWE.

The modulus is chosen for speed. Since 256 divides 3328 = q − 1, the number ζ = 17 is a primitive 256th root of unity modulo q, and a number-theoretic transform splits X256 + 1 into 128 quadratic factors. Multiplying two polynomials then takes a few thousand small multiplications, transforms included, instead of the 65,536 of the schoolbook method.

The encryption scheme underneath

ML-KEM is built on a simpler public-key encryption scheme, K-PKE, which encrypts a 32-byte message m. Small polynomials are sampled from a centred binomial distribution CBDη, whose coefficients lie between −η and η; the matrix A is expanded from a 32-byte seed ρ with SHAKE128, so the public key carries the seed instead of the matrix.

K-PKE.KeyGen
  A ← expanded from seed ρ
  s, e ← CBD(η1)                  small, secret
  t = A·s + e
  encryption key (t, ρ);  decryption key s

K-PKE.Encrypt(t, ρ, m; randomness)
  r ← CBD(η1);  e1, e2 ← CBD(η2)
  u = Aᵀ·r + e1
  v = tᵀ·r + e2 + ⌈q/2⌉·m          each bit of m becomes 0 or ⌈q/2⌉
  ciphertext (Compress(u, du), Compress(v, dv))

K-PKE.Decrypt(s, u, v)
  w = v − sᵀ·u
  m = each coefficient of w rounded to 0 or ⌈q/2⌉

An outline of FIPS 203's K-PKE; the standard fixes every encoding, sampling and hashing step.

Decryption works because w = ⌈q/2⌉·m + (eTr + e2 − sTe1) plus rounding from compression, and the bracketed error is a sum of products of small polynomials. It is almost always smaller than q/4 in every coefficient, so rounding recovers m. Almost always is not always: the chance that some coefficient overflows is the decapsulation failure rate, which FIPS 203 gives as 2−138.8, 2−164.8 and 2−174.8 for the three parameter sets.

Compression drops low-order bits of u and v to shorten the ciphertext. It adds a little more error, which is part of the same failure budget.

From encryption to a KEM

K-PKE on its own is only secure against passive attackers: someone who can submit modified ciphertexts and watch what the decrypter does can learn the secret key. ML-KEM wraps it in a variant of the Fujisaki–Okamoto transform, which makes decryption check its own work:

Encaps(ek)
  m ← 32 random bytes
  (K, r) = G(m ‖ H(ek))
  c = K-PKE.Encrypt(ek, m; r)
  return (K, c)

Decaps(dk, c)                     dk holds s, ek, H(ek) and a random z
  m' = K-PKE.Decrypt(s, c)
  (K', r') = G(m' ‖ H(ek))
  c' = K-PKE.Encrypt(ek, m'; r')
  if c' = c:  return K'
  else:       return J(z ‖ c)        implicit rejection

G, H and J are SHA3-512, SHA3-256 and SHAKE256.

Because all the encryption randomness is derived from m, the decrypter can re-encrypt and compare. A tampered ciphertext fails the comparison, and instead of reporting an error, Decaps returns a key derived from a secret value z and the ciphertext. The attacker gets a random-looking key either way and learns nothing from the difference; the handshake simply fails later, as it would with a wrong key. Hofheinz, Hövelmanns and Kiltz give the modular analysis of transforms of this kind.

FIPS 203 also requires input checks that Kyber's specification did not include: an encapsulation key whose coefficients are not reduced modulo q must be rejected, and a decapsulation key must match the hash of the encapsulation key stored inside it.

Parameters and sizes

From FIPS 203, Tables 1 to 3. All three sets use n = 256 and q = 3329.
kη1η2dudvCategoryFailure rate
ML-KEM-51223210412−138.8
ML-KEM-76832210432−164.8
ML-KEM-102442211552−174.8
Sizes in bytes, from FIPS 203, Table 3.
Encapsulation keyDecapsulation keyCiphertextShared secret
ML-KEM-5128001,63276832
ML-KEM-7681,1842,4001,08832
ML-KEM-10241,5683,1681,56832

A security category is a comparison, not a count of bits: category 1 means breaking the scheme takes at least as many resources as recovering an AES-128 key by search, category 3 an AES-192 key, and category 5 an AES-256 key. FIPS 203 recommends ML-KEM-768 as the default, as providing a large security margin at a reasonable cost.

Security in practice

The best known attacks on the mathematics are lattice reduction, in primal and dual forms, and their cost is estimated rather than measured: the estimates depend on models of how BKZ and lattice sieving scale, and on how memory is costed. Whether ML-KEM-512 comfortably meets category 1 was argued in public during standardisation, and the answer depends on those models. The page on Kuperberg's algorithm discusses the same issue for quantum costs; any claimed security level is a claim about a cost model.

The failures so far have been in implementations. In 2024, KyberSlash showed that several implementations, including the reference code, divided by q using instructions whose timing depends on the secret, and recovered keys within minutes to hours on a Raspberry Pi 2 and on a Cortex-M4. The affected libraries were patched. Side channels and faults in decapsulation, where the secret is used, remain the thing to review.

Where it stops

ML-KEM would fall to an efficient algorithm for module-LWE at these dimensions, classical or quantum. None is known, and the structure it adds over plain LWE has not yielded an attack on these parameters. Because ML-KEM is NIST's only standardised KEM, NIST selected HQC in 2025 as a second one based on different mathematics, as a backup in case a weakness is found in ML-KEM.

Primary sources

  1. NIST, FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
  2. O. Regev, "On lattices, learning with errors, random linear codes, and cryptography", Journal of the ACM 56 (2009)
  3. A. Langlois and D. Stehlé, "Worst-case to average-case reductions for module lattices", Designs, Codes and Cryptography 75 (2015)
  4. D. Hofheinz, K. Hövelmanns and E. Kiltz, "A modular analysis of the Fujisaki-Okamoto transformation", TCC 2017
  5. D. J. Bernstein et al., "KyberSlash: exploiting secret-dependent division timings in Kyber implementations", TCHES 2025
  6. NIST IR 8545, Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (2025)
  7. IETF, "Post-quantum hybrid ECDHE-MLKEM key agreement for TLSv1.3" (draft-ietf-tls-ecdhe-mlkem)