How ML-KEM Works: From Noisy Equations to a Shared Secret

In the sysadmin migration post I treated ML-KEM as a black box you plug into TLS. Here is the other view: what that black box actually does, following FIPS 203 - the Module-Lattice-Based Key-Encapsulation Mechanism Standard published in August 2024.

ML-KEM is the standardized form of CRYSTALS-Kyber. Three algorithms, three parameter sets, one hard problem: Module Learning With Errors (Module-LWE). The goal of this post is not to re-implement the standard line by line but to build a mental model.

What a KEM is

A key-encapsulation mechanism is basically three algorithms for establishing a shared secret over a public channel:

1. KeyGen - Alice produces an encapsulation key (public) and a decapsulation key (private).
2. Encaps - Bob takes Alice's encapsulation key, samples randomness, and outputs a shared secret K plus a ciphertext c.
3. Decaps - Alice takes c and her decapsulation key and recovers her copy K'.

Under the right conditions, K' = K, and that 256-bit value can be used directly as a shared secret key for AES-GCM, HKDF, and friends. That is the TLS use case: replace (or hybridize with) X25519 / ECDH.

FIPS 203 is careful about naming. It avoids "public key / private key" because ML-KEM sits on top of a component PKE that has its own encryption and decryption keys. The standard talks about encapsulation / decapsulation keys for the KEM and encryption / decryption keys for the inner scheme.

The hard problem: Module-LWE

Security rests on Module Learning With Errors. Before the "module" part, two ideas need to be clear: what a ring is here, and why noise turns easy linear algebra into a hard problem.

Quick refresh: what is a ring?

In school algebra you mostly multiply and add numbers. A ring is a set where you can still do those two things, with familiar rules (associative addition, a zero, multiplication distributes over addition), but without needing every non-zero element to have a multiplicative inverse.

Two rings show up in this story:

1. Integers modulo q, written ℤ_q. Think "clock arithmetic" with q hours: add and multiply as usual, then wrap around when you pass q. In ML-KEM, q = 3329.
2. Polynomials with those coefficients, cut down so they never grow forever. ML-KEM uses polynomials of degree less than n = 256, with the wrap rule X^256 = -1. You add coefficient-wise; you multiply like ordinary polynomials, then reduce with that rule. That object is the ring R_q.

So an "element of R_q" is just a list of 256 numbers between 0 and q-1, with a defined way to multiply two such lists. You do not need the full abstract algebra course - you need "we compute with modular numbers, and also with short polynomials of those numbers."

Learning With Errors: why the noise matters

Start with Regev's LWE (2005), still over plain ℤ_q.

Without noise, someone publishes something like a matrix A and a product t = A · s for a secret vector s. Recovering s is ordinary linear algebra: Gaussian elimination (or an equivalent solver) finishes the job. Exact equations are easy.

LWE changes one thing: the publisher adds a small error e and releases

t = A · s + e

instead of the clean product.

That single change is the whole security idea:

• The equations are almost linear in s, but not exactly.
• Gaussian elimination assumes exact equalities. Noise makes those equalities wrong, so the textbook solver does not recover s.
• If you try to "ignore" the noise or guess it, the search space explodes. If the noise were huge, the samples would look random but decryption later would also fail. Cryptography walks a narrow path: noise large enough to hide s, small enough that the legitimate owner can still cancel and read a message.

In short: exact linear systems are easy; slightly wrong linear systems (LWE) are believed hard, including for quantum algorithms we know today.

Module-LWE: same idea, richer coefficients

Module-LWE is the same noisy-equation story, but each entry lives in the polynomial ring R_q instead of in plain ℤ_q. The secret s becomes a short list of ring elements (length k, the module rank). You still get a public matrix A and a noisy product t ≈ A · s. The hardness claim is the same shape: without s, those samples should look random.

ML-KEM always uses n = 256 and q = 3329. Larger parameter sets mainly increase k (2, 3, or 4), which makes the module bigger and the instance harder - at the cost of larger keys and ciphertexts.

Intuition that carries through the rest of the post:

• Public key ≈ "here is a matrix A and a noisy product t ≈ A · s"
• Encryption ≈ "combine those equations randomly and hide a message in the noise margin"
• Decryption ≈ "use s to cancel the linear part and read what remains"

That is K-PKE in one sentence. ML-KEM wraps it so that adaptive ciphertext attacks do not break the shared secret.

Construction in two layers

FIPS 203 builds ML-KEM in two steps:

K-PKE is not approved as a stand-alone encryption scheme. It is only a subroutine. Using it directly would give you something closer to IND-CPA security - fine against passive eavesdroppers, not fine against an adversary who can submit crafted ciphertexts and watch how you react. The FO transform upgrades that to IND-CCA2, which is what you want for real protocols.

Layer 1: K-PKE key generation

Informally, Alice samples:

• a public matrix A (expanded from a 32-byte seed ρ via SHAKE128 / XOF)
• a secret vector s with small coefficients
• an error vector e with small coefficients

and publishes:

$$t = A \cdot s + e$$

The encapsulation key is essentially (t, ρ). The decryption key is s (stored in NTT form in the actual algorithm).

Small coefficients come from a centered binomial distribution (CBD), not from a uniform draw over all of R_q. That keeps the noise small enough that decryption still works, but large enough that t does not leak s.

Layer 2: K-PKE encryption and decryption

Bob wants to "encrypt" a 32-byte message m. He samples another small vector y and more noise, forms a new noisy equation from the public system, and embeds m into the constant term:

$$u \approx A^\top \cdot y,\qquad v \approx t^\top \cdot y + \mu(m)$$

where μ(m) encodes each bit of m into a coefficient of a polynomial (one bit per coefficient - and there are 256 coefficients, so 32 bytes fit cleanly).

Alice decrypts by computing something equivalent to:

$$w \approx v - s^\top \cdot u$$

The linear terms cancel (up to accumulated noise). What remains is a noisy version of μ(m). Compression / rounding recovers m.

That cancellation is why the scheme works, and why noise parameters matter. Too little noise: insecure. Too much noise: decapsulation failures. FIPS 203 quotes failure rates that are astronomically small (2^-138.8 for ML-KEM-512, even smaller for the larger sets).

Compression

Ciphertexts are not sent as full 12-bit coefficients modulo q. They are compressed with parameters d_u and d_v:

$$\text{Compress}_d(x) = \left\lceil \frac{2^d}{q} \cdot x \right\rfloor \bmod 2^d$$

You lose some precision on purpose. That shrinks the ciphertext and adds a controlled amount of extra noise that decryption must still tolerate. It is one of the reasons ML-KEM ciphertexts are hundreds of bytes instead of kilobytes of raw ring elements.

From K-PKE to ML-KEM: the FO transform

K-PKE alone is not enough for TLS. Against a passive eavesdropper it is fine in spirit. Against an active adversary - someone who can send crafted ciphertexts and watch how your Decaps behaves - a bare PKE of this kind is fragile. Decryption failures, malleated ciphertexts, and reaction leaks can chip away at the secret.

The Fujisaki-Okamoto (FO) transform is a general recipe (1990s, with many modern variants) for turning a weaker public-key encryption scheme into a KEM that resists those active attacks. FIPS 203 applies one specific FO-style construction on top of K-PKE. That wrapper is ML-KEM.

What FO is trying to achieve

Three goals, in plain language:

1. Derive a shared secret K, not "decrypt arbitrary user data." The inner message m is random seed material, not an email body.
2. Make encryption deterministic given m. The randomness used to encrypt (r, the "coins") is computed from m (and a hash of the public key), not chosen freely. Same m always produces the same ciphertext.
3. Check honesty on decapsulation. After decrypting a candidate m', re-encrypt it with the derived coins and demand an exact match with the received ciphertext. If the match fails, do not return a useful key.

That re-encrypt check is the heart of FO. An attacker who flips bits in c may still get some m' out of K-PKE, but re-encryption will not reproduce the tampered c. The check fails, and the KEM refuses to hand out the real session key.

Encapsulation (what Bob does)

1. Sample a random 32-byte string m.
2. Hash m together with H(ek) (a digest of Alice's encapsulation key). Split the digest into:
   • K - the shared secret Bob will keep
   • r - the coins that will drive K-PKE encryption
3. Run K-PKE encrypt on m using randomness r → ciphertext c.
4. Output (K, c). Send c to Alice; keep K.

Because r is a deterministic function of m and the public key, Alice will be able to redo the same encryption later.

Decapsulation (what Alice does)

1. Run K-PKE decrypt on c → candidate m'.
2. Recompute (K', r') the same way Encaps would, from m' and H(ek).
3. Re-encrypt m' under K-PKE with coins r' → candidate ciphertext c'.
4. If c' = c, the ciphertext was the honest encapsulation of m'. Return K'.
5. If not, implicitly reject: return J(z ‖ c) instead. Here z is a secret random value stored in Alice's decapsulation key. The output still looks like a 32-byte key, but it is unrelated to Bob's K.

Why the design details matter

Coins (r). In ordinary randomized encryption you pick fresh randomness every time. FO forbids that for the inner encrypt: coins come from hashing m. That is what makes the re-encrypt check possible. "Coins" here just means the random tape of the encryption algorithm - in the lab and in the standard, a seed that expands into y, e₁, e₂, and friends.

Implicit rejection. Decaps always returns 32 bytes. It does not return "fail." An attacker who tampers with c gets a pseudorandom key from J(z ‖ c), not a distinguishable error. That blocks reaction attacks that rely on "did Decaps accept?" and helps constant-time implementations avoid validity branches that leak through timing.

Binding to the encapsulation key. Deriving K and r from m ‖ H(ek) ties the shared secret to Alice's intended public key. That closes attacks where Bob thinks he encapsulated to Alice but the transcript was pointed at another key.

FIPS 203 stores H(ek) and z inside the decapsulation key so Alice already has everything Decaps needs - no awkward re-hashing of the full key, no sampling fresh reject material per call.

One-line summary

K-PKE moves a short seed through noisy module equations. FO decides which seed is allowed, turns it into a session key K, and rejects (quietly) anything that was not an honest encapsulation of that seed.

Why the NTT shows up everywhere

Most of ML-KEM is "multiply things in R_q." A naive multiply of two degree-255 polynomials means a lot of coefficient work - fine in a paper, painful in TLS handshakes.

The Number-Theoretic Transform (NTT) is the modular-arithmetic cousin of the FFT you may know from signal processing. Same job, different domain:

• FFT idea: rewrite a signal so convolution becomes pointwise multiply, then convert back.
• NTT idea: rewrite a ring element so polynomial multiplication (the expensive part) becomes many tiny independent multiplies, then convert back with NTT⁻¹.

You can treat NTT as a change of representation, not as a new cryptographic idea:

1. Coefficients form - good for adding noise, encoding message bits, compression.
2. NTT form - good for matrix-vector products like A · s or Aᵀ · y.

ML-KEM does not treat NTT as an optional speed hack. The algorithms are specified with it. Public material such as t (and the stored secret s) is kept in NTT form so encryptors and decryptors do not pay convert-and-multiply costs on every call. When a step needs coefficient-wise work (sample noise, embed μ(m), compress), it converts back.

You do not need the butterfly diagram to review an implementation. You do need:

• NTT / NTT⁻¹ must be exact - a wrong transform is a broken scheme, not a slow correct one
• keys may look like "random" coefficient lists even though they are already transformed
• side-channel research often targets NTT and sampling, because that is where the hot loops and secret-dependent work live - more than the FO wrapper text

Parameter sets

Three approved sets, increasing security and cost:

Set	NIST category	k	Encaps key	Decaps key	Ciphertext	Shared secret
ML-KEM-512	1	2	800 B	1632 B	768 B	32 B
ML-KEM-768	3	3	1184 B	2400 B	1088 B	32 B
ML-KEM-1024	5	4	1568 B	3168 B	1568 B	32 B

k is the module rank - the dimension of the Module-LWE instance. Larger k means bigger matrices, bigger keys, bigger ciphertexts, harder problem.

NIST's guidance in FIPS 203 is blunt: use the strongest set you can, and prefer ML-KEM-768 as the default. That matches what you see in hybrid TLS deployments: category 3 is the practical sweet spot for most systems that already tolerate ~1 KB of handshake overhead.

Security categories here are not "128-bit / 192-bit / 256-bit" slogans. They are claims relative to breaking AES-128, AES-192, or AES-256 (categories 1, 3, 5) under realistic cost models. Lattice security estimates are an active research area; the categories are how NIST communicates the intended strength without pretending cryptanalysis is settled forever.

What you should take into an implementation review

If you are reading OpenSSL, BoringSSL, or a liboqs wrapper rather than FIPS 203 itself, these are the checks that map back to the standard:

1. Do not expose K-PKE. Only the ML-KEM KeyGen / Encaps / Decaps APIs are approved.
2. Randomness strength. RBG security must be at least 128 / 192 / 256 bits for 512 / 768 / 1024 respectively.
3. Input checking. Encaps checks encapsulation-key length and modulus encoding. Decaps checks ciphertext length, decapsulation-key length, and the stored hash of the encapsulation key.
4. Destroy intermediates. Coins, decrypted m', and the implicit-reject flag are sensitive. The standard requires they not linger after the call returns.
5. No floating point. Compression and decompression are defined with integer rounding. FP rounding bugs become correctness bugs, which become security bugs under FO.
6. Seed expansion. A 64-byte seed (d, z) can regenerate the full key pair. Treat that seed like the decapsulation key.

How this connects to the rest of the stack

In TLS you almost never "encrypt application data with ML-KEM." You run Encaps/Decaps during the handshake, feed the 32-byte shared secret into the key schedule (often hybridized with X25519), and then AES-GCM or ChaCha20-Poly1305 does the heavy lifting.

That split is why migration feels strange at first: the post-quantum part is a key establishment swap, not a new record-layer cipher. I covered the operational inventory in the sysadmin post. This post is the mathematical reason that swap is possible at all - noisy module equations, a fragile PKE, and a transform that makes active attacks unproductive.

Further reading

• Mini ML-KEM lab - interactive walkthrough with mini parameters ($n=4$, $q=41$), including NTT and the Fujisaki-Okamoto layer
• FIPS 203 - the normative reference this post tracks
• CRYSTALS-Kyber round-3 specification - the submission ML-KEM derives from (Appendix C of FIPS 203 lists the deltas)
• SP 800-227 - how to use KEMs safely in applications
• My earlier notes: PQC eight years after the thesis and PQC migration for sysadmins