Inside ML-KEM

KEM, not encryption

ML-KEM is a key-encapsulation mechanism (KEM). It doesn't encrypt your data. It does one job: get the same 32-byte random secret to two parties. Then a symmetric cipher such as AES-GCM does the bulk work. The interface has three functions:

• KeyGen() → (ek, dk): an encapsulation key (public) and a decapsulation key (private).
• Encaps(ek) → (K, c): a fresh shared secret K and a ciphertext c to send.
• Decaps(dk, c) → K: recovers the same K.

FIPS 203 deliberately says "encapsulation key" and "decapsulation key" rather than public and private key. We'll follow it. Under the hood are two layers. K-PKE is a Module-LWE public-key encryption scheme, the bigger sibling of the Regev scheme from the last lesson. A Fujisaki–Okamoto-style transform then wraps it to make the KEM safe against active attackers.

The parameters

Every parameter set uses n = 256 and q = 3329. Five numbers vary (FIPS 203, Table 2):

Sizes are in bytes, and the shared secret is always 32 bytes. k is the module rank. η1 and η2 set the width of the noise, and du, dv set how many bits each ciphertext coefficient is compressed to. The sizes fall straight out of these:

• ek = 384·k + 32. k polynomials × 256 coefficients × 12 bits = 384·k bytes, plus the 32-byte seed ρ for the matrix.
• ciphertext = 32·(d_u·k + d_v). k polynomials at du bits per coefficient plus one at dv bits. For ML-KEM-768: 32·(30 + 4) = 1088.
• dk = 768·k + 96. The K-PKE secret (384·k), a copy of ek (384·k + 32), H(ek) (32) and the implicit-rejection seed z (32).

K-PKE: the noisy core

Here is the inner encryption scheme, simplified from FIPS 203 Algorithms 13–15. Bold letters are vectors or matrices of polynomials in R_q = Z_q[X]/(X256+1).

K-PKE.KeyGen(d):
  (ρ, σ) = G(d ‖ k)                  # G = SHA3-512
  Â = SampleNTT(ρ)                   # k×k matrix, generated directly in NTT form
  s, e ← CBD_η1(PRF(σ, ·))           # small secret and error
  t = A·s + e                        # computed as Â∘NTT(s) + NTT(e)
  return ek = (t, ρ), dk_pke = s

K-PKE.Encrypt(ek, m, r):             # m: 32 bytes = 256 bits; r: 32 bytes of coins
  y ← CBD_η1(PRF(r, ·)); e1, e2 ← CBD_η2(PRF(r, ·))
  u  = Aᵀ·y + e1
  v  = tᵀ·y + e2 + Decompress_1(m)   # each bit becomes 0 or ⌈q/2⌋ = 1665
  return c = (Compress_du(u), Compress_dv(v))

K-PKE.Decrypt(s, c):
  w = Decompress_dv(c2) − sᵀ·Decompress_du(c1)
  return m = Compress_1(w)           # round each coefficient to 0 or 1

CBD_η is the centered binomial distribution: add η random bits, subtract another η. With η = 2 every coefficient lands in {−2, …, 2}. It's cheap to sample in constant time from a hash output, which is why ML-KEM uses it rather than a Gaussian.

Why decryption works: substitute and the large terms cancel, exactly as in plain LWE.

w = v − sᵀu = eᵀy + e2 − sᵀe1 + (compression errors) + ⌈q/2⌋·m

Every term except the last is a sum of products of small numbers. As long as each coefficient of that noise stays below q/4 ≈ 832 in absolute value, rounding recovers m. FIPS 203 calls a miss a decapsulation failure and bounds its probability per parameter set (the table above).

Compression: trading bits for noise

Coefficients are 12-bit numbers mod 3329, but ciphertexts don't send all 12 bits. FIPS 203 defines, for d < 12:

Compress_d(x)   = ⌈(2^d / q) · x⌋ mod 2^d
Decompress_d(y) = ⌈(q / 2^d) · y⌋

This keeps only the top d bits of each coefficient. ML-KEM-768 sends u at 10 bits and v at just 4. The rounding error is simply more noise, and it's already budgeted into the failure rate. FIPS 203 adds a pointed rule: these divisions "shall not" be computed in floating point. As you'll see in implementation pitfalls, how you compute that division turned out to matter a great deal.

The NTT: why q = 3329

Multiplying two degree-255 polynomials naively costs 256² = 65,536 coefficient multiplications. The number-theoretic transform (NTT) is a fast Fourier transform over Z_q. It converts polynomials into a form where multiplication is (almost) coefficient-by-coefficient, in O(n log n) time.

The NTT needs roots of unity mod q. FIPS 203 picks q = 3329 = 28·13 + 1, so Z₃₃₂₉ has primitive 256th roots of unity; the standard uses ζ = 17. There are no primitive 512th roots, though, so X256 + 1 splits into 128 quadratic factors X2 − ζ2·BitRev7(i)+1, not 256 linear ones. In NTT form, a polynomial is 128 pairs, and multiplication is 128 small degree-1 products (MultiplyNTTs and BaseCaseMultiply in the standard). This is sometimes called an "incomplete" NTT.

Two design consequences:

• The matrix is born in NTT form. SampleNTT expands ρ with SHAKE128 straight into Â, so no transform is needed for it.
• Small q, small keys. 3329 fits in 12 bits, which keeps keys and ciphertexts compact while leaving room for the noise.

The FO transform and implicit rejection

K-PKE alone is only secure against passive eavesdroppers (IND-CPA). An active attacker can send crafted ciphertexts and watch how decryption behaves, learning the secret bit by bit. The Fujisaki–Okamoto (FO) transform closes that hole by making decapsulation verify that the ciphertext was honestly produced.

ML-KEM.Encaps(ek):
  m ← 32 random bytes
  (K, r) = G(m ‖ H(ek))              # H = SHA3-256, G = SHA3-512
  c = K-PKE.Encrypt(ek, m, r)        # coins r are derived, not random
  return (K, c)

ML-KEM.Decaps(dk, c):                # dk = (s, ek, h = H(ek), z)
  m' = K-PKE.Decrypt(s, c)
  (K', r') = G(m' ‖ h)
  K̄  = J(z ‖ c)                      # J = SHAKE256, 32-byte output
  c' = K-PKE.Encrypt(ek, m', r')     # re-encrypt!
  if c ≠ c': K' = K̄                  # implicit rejection
  return K'

Because encryption is deterministic given (m, r) and r is derived from m, the receiver can re-run encryption and check it gets the identical ciphertext. Any tampering, or any ciphertext the attacker built by hand, fails that check.

What happens on failure is the clever part. ML-KEM does not return an error. It returns K̄ = J(z ‖ c), a pseudorandom key derived from a secret seed z. The sender's key and the receiver's key simply don't match, and the protocol above fails later, when a MAC or AEAD tag doesn't verify. That's implicit rejection: the attacker can't tell "malformed" from "valid but different," so decapsulation stops being an oracle. FIPS 203 is explicit that the internal match/mismatch flag is secret: it "shall be destroyed" and must not be output "in any form."

Run the toy with η = 2: the noise bars stay far from the ±q/4 line and the secrets match. Tick the tamper box. Often m′ still decrypts correctly, yet the re-encryption check fails and Alice silently returns K̄. Then choose a huge η and watch a genuine decryption failure surface the same way: different keys, no error message.

Input checks the standard requires

FIPS 203 wraps the internal algorithms with mandatory input validation:

• Encapsulation key check: the right length (384·k + 32), plus a modulus check: decoding and re-encoding the 12-bit coefficients must give back the same bytes, so every coefficient is in [0, q−1]. Assurance can come from elsewhere (see SP 800-227), but encapsulation "shall not" run on an unchecked key.
• Decapsulation checks: the ciphertext length must be exactly 32·(d_u·k + d_v), on every call. The decapsulation key must have the right length and pass a hash check: the stored H(ek) must match a fresh hash of the embedded ek.

Randomness requirements scale with the parameter set: the random bit generator must provide at least 128, 192 or 256 bits of security strength for ML-KEM-512, -768 and -1024 respectively.

Questions

Get five of six right to mark the lesson complete. They also feed the final exam.

Sources

• NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard
• NIST SP 800-227: Recommendations for Key-Encapsulation Mechanisms
• Bos et al., CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM
• CRYSTALS-Kyber reference implementation (pq-crystals)

Drawn byKyeson Blake Utley

CourseQuantum Defense

Sheet14 of 18

PartIII · Engineer

Rev.18 Oct 2026

Sources4 cited

Found an error?Send a correction