Inside ML-KEM: Noise Growth from Keygen to Decapsulation

Every KEM in deployment hides a decision about how much noise to add and where to cut it off. ML-KEM, standardised as FIPS 203, is a module-lattice KEM where that decision appears three times: in the magnitude of the secret and error polynomials generated at key generation, in the compression applied to the ciphertext before it is sent, and in the threshold used during decapsulation to decide whether the result is valid. Tracking the error term through the three operations shows why the parameters have the values they do and why the decapsulation failure probability is not negligible by accident.

The ring and the two structural tricks

All arithmetic takes place in $R_q = \mathbb{Z}_q[X]/(X^{256}+1)$ with $q = 3329$, for every parameter set. A ring element is a polynomial with 256 coefficients, each an integer in $[0, 3328]$. Multiplication is polynomial multiplication followed by reduction modulo $X^{256}+1$, which maps $X^{256}$ to $-1$ and $X^{257}$ to $-X$, and so on. The modulus choice is not arbitrary: $q - 1 = 3328 = 2^8 \cdot 13$, so $q$ factors as $256 \cdot 13 + 1$ and a primitive 256th root of unity exists modulo $q$. That gives the number-theoretic transform, an analogue of the FFT over the field, which multiplies two ring elements in $O(n \log n)$ field operations rather than $O(n^2)$. Implementations use an incomplete NTT that stops partway to avoid bit-reversal and keeps intermediate products in 16-bit words.

The second trick is how the standard splits a ring element into two halves. The trace map $T(a) = a(X) + a(-X)$ has all even coefficients equal to twice a coefficient and all odd coefficients vanish, and it maps $R_q$ onto a subring isomorphic to $\mathbb{Z}q^{128}$. Every element can be written as $a = a{\text{even}}(X^2) + X \cdot a_{\text{odd}}(X^2)$, splitting into two elements of a smaller ring of dimension 128. Encryption and decryption in ML-KEM are carried out in this split domain, so the expensive multiplications operate on 128-coefficient halves and the noise analysis is done in the smaller ring where the bounds are tighter.

The secret is not one polynomial but a vector. ML-KEM-768 uses $k = 3$ polynomials per vector and occupies security category 3. ML-KEM-512 uses $k = 2$ at category 1 and ML-KEM-1024 uses $k = 4$ at category 5. The vector dimension is what scales with the security target, whereas $q$ and $n = 256$ are fixed for all three sets.

Key generation and the shape of the public key

Key generation samples a $k$-dimensional vector $s$ and a $k$-dimensional vector $e$, both with coefficients drawn from a centred binomial distribution over ${-2, \dots, 2}$ rather than from a discrete Gaussian. Sampling is done by taking eight bits of the output of a pseudorandom function, splitting them into four pairs, and subtracting the per-pair bit count from the pair count, which yields exactly the centred binomial $\eta = 2$ distribution without table lookups. The alternative, rejection sampling on a discrete Gaussian, is what early lattice schemes used and what made constant-time implementation painful; the centre binomial has integer-valued support and can be sampled with shifts and adds.

The matrix $A$ is not transmitted. It is generated deterministically from a 32-byte public seed by the XOF defined in FIPS 202, with each entry produced by hashing a domain-separated string of the seed and the row and column indices. This is a compression of roughly 1.5 KB per parameter set: a $3 \times 3$ matrix of 256-coefficient polynomials would be more than 24 KB raw and is instead produced on demand from 32 bytes. It also makes the public key deterministic given the seed, which matters for the derandomised forms used in some protocols.

The public key is

$$t = A s + e,$$

where products are vector-matrix products over $R_q$, plus the seed. The secret key holds $s$ and the seed used to derive the encryption randomness that validates the ciphertext during decapsulation. For ML-KEM-768, the public key encodes as 1184 bytes because each coefficient of $t$ is serialised in 12 bits and the seed adds 32 bytes.

Encryption: compression is where the noise budget is spent

Encapsulation samples a short vector $r$ and short errors $e_1$ (a $k$-vector) and $e_2$ (a single polynomial), and a small polynomial encoding a message bit string. The message is reduced from a 32-byte hash output to a polynomial whose coefficients are 0 or $\lceil q/2 \rceil$, one bit per coefficient. The ciphertext consists of

$$u = A^T r + e_1, \qquad v = t^T r + e_2 + m,$$

where $m$ carries the message. Decryption computes $v - s^T u$, which expands to

$$m + e^T r + e_2 - s^T e_1.$$

The noise term $e^Tr + e_2 - s^Te_1$ is a sum of $k^2$ products of small coefficients. Each product of two centred-binomial values is bounded by 4 in absolute value, so the sum is bounded by $4k^2$ in the worst case, and the concentration is much tighter in practice. With $q = 3329$ and the message coefficient at $q/2 = 1664$, half the modulus, decryption succeeds whenever the noise stays below roughly $q/4$ in magnitude since the rounding boundary sits at $q/4$ and $3q/4$. For $k = 3$ the worst-case bound $4k^2 = 36$ is far below the 832 boundary, which is the margin the parameter set depends on.

The compression step then discards information. The $u$ component is compressed from 12 bits per coefficient to 10 bits, and $v$ from 12 to 4 bits, by rounding each coefficient to the nearest multiple of $q/2^{d}$ and storing the resulting $d$-bit value. That rounding introduces a decompression error of up to $q/2^{d+1}$ per coefficient. For $v$ with $d = 4$, that is about 104. The noise bound and the compression error are added together before the decryption threshold is applied; this is why the number of bits dedicated to $v$ is small and why increasing compression to save bandwidth directly raises the failure rate. For ML-KEM-768 the ciphertext is 1088 bytes, made of $3 \times 320$ bytes of compressed $u$ and 128 bytes of compressed $v$.

Key encoding and why the matrix is not sent

The public key bytes are not a ciphertext and can be stored once per long-term key, but they still matter for protocol compatibility. Each coefficient of $t$ is encoded in 12 bits, packed two coefficients per 3 bytes, which is why the ML-KEM-768 public key is $3 \times 256 \times 12 / 8 = 1152$ bytes plus the 32-byte seed, totalling 1184. The secret key is stored in the “expanded” form used during decapsulation and includes the matrix seed, so a decapsulation can regenerate $A$ without storing it. Serialising $A$ instead would grow the secret key by the same amount the public key saves.

The 12-bit encoding wastes bandwidth in a specific sense: $q = 3329$ needs 12 bits but only uses values up to 3328, so about 19 percent of the encoding space is unused. The alternative, packing coefficients in fewer bits via entropy coding, would make parsing data-dependent and complicate constant-time validation of untrusted public keys. Fixed-width encoding is the choice that keeps the decoder branch-free, and the same reasoning appears in the ciphertext compression parameters, where the $u$ and $v$ components use 10 and 4 bits respectively rather than an entropy-optimal scheme.

A public key is untrusted input in most protocols. A malicious peer can send a key whose coefficients are all valid 12-bit values but are not reduced modulo $q$, or whose seed produces a matrix $A$ that is all zeros. The standard requires the decoder to accept only canonical encodings, and implementations must reject values at or above $q$ rather than reducing them; a lax decoder that reduces mod $q$ accepts multiple encodings of the same key, which breaks the hash of the public key used inside encapsulation and can produce two different session keys from what the protocol believes is one identity.

Decapsulation and the re-encryption check

Decapsulation recovers the message candidate by the computation above, then takes the hash of that candidate together with the ciphertext hash, re-encrypts deterministically from the recomputed randomness, and compares the result against the received ciphertext in constant time. On a mismatch, it does not return an error: it substitutes a pseudorandom key derived from the secret and the ciphertext, so the caller receives a key that cannot be distinguished from a valid one without knowing the secret. This is the Fujisaki-Okamoto transform in its implicit-rejection form, and it is what upgrades the scheme from IND-CPA to IND-CCA.

The failure probability is bounded by the probability that the noise plus compression error crosses the rounding boundary. For ML-KEM-768 the standard reports a decapsulation failure probability below $2^{-164}$ in the relevant sense, and the parameters were chosen with that bound as a constraint rather than measured after the fact. The bound is not zero, and that is deliberate: tightening it would require a larger $q$ or less compression, both of which cost bandwidth or key size. The security proof treats a nonzero failure rate as a parameter of the adversary’s advantage, which is why the bound is published in the standard and why implementations must not deviate from the specified rounding.

A recurring implementation problem is that the deterministic re-encryption is where the whole scheme’s correctness is verified, so any discrepancy in the arithmetic between encapsulation and decapsulation surfaces as a spurious key rather than as an error. Bit-exact conformance to the reference arithmetic in the standard is the mitigation, including the exact order of the NTT butterflies. That is the same class of concern that arises in constant-time comparison and early-exit code, where a single data-dependent branch converts a correctness detail into a leak.