Why Decryption Works

This is the note to follow line by line. It is short, it is the mathematical heart of the scheme, and everything about the parameter choices falls out of it.

01.Decryption

Bob receives $c$, decompresses it back to $\mathbf{u}$ and $v$, and computes

$$w \;=\; v - \mathbf{s}^\top \mathbf{u} \;\in\; R_q .$$

Then he decodes each coefficient of $w$: the bit is $1$ if the coefficient is closer to $\lceil q/2 \rceil$ than to $0$, and $0$ otherwise.

That is the whole algorithm. One inner product and 256 comparisons. The interesting part is why it works.

02.The cancellation

Ignore compression for the moment and substitute what $v$ and $\mathbf{u}$ actually are.

From encryption, $v = \mathbf{t}^\top \mathbf{r} + e_2 + \text{Encode}(m)$ and $\mathbf{u} = A^\top \mathbf{r} + \mathbf{e}_1$. So

$$\begin{aligned} v - \mathbf{s}^\top \mathbf{u} &= \bigl(\mathbf{t}^\top \mathbf{r} + e_2 + \text{Encode}(m)\bigr) - \mathbf{s}^\top\bigl(A^\top \mathbf{r} + \mathbf{e}_1\bigr) \\[2pt] &= \mathbf{t}^\top \mathbf{r} \;-\; \mathbf{s}^\top A^\top \mathbf{r} \;+\; e_2 \;-\; \mathbf{s}^\top \mathbf{e}_1 \;+\; \text{Encode}(m) . \end{aligned}$$

Now use what key generation guaranteed: $\mathbf{t} = A\mathbf{s} + \mathbf{e}$. Transposing gives $\mathbf{t}^\top = \mathbf{s}^\top A^\top + \mathbf{e}^\top$. Substitute that into the first term:

$$v - \mathbf{s}^\top \mathbf{u} \;=\; \bigl(\mathbf{s}^\top A^\top + \mathbf{e}^\top\bigr)\mathbf{r} \;-\; \mathbf{s}^\top A^\top \mathbf{r} \;+\; e_2 \;-\; \mathbf{s}^\top \mathbf{e}_1 \;+\; \text{Encode}(m) .$$

The two copies of $\mathbf{s}^\top A^\top \mathbf{r}$ cancel.

That cancellation is the entire construction. It is why encryption multiplies by $A^\top$ while key generation multiplies by $A$, and it is why the two ciphertext components have the shapes they do. Everything else in ML-KEM is arranged so that this one term appears twice with opposite signs.

What is left is

$$v - \mathbf{s}^\top \mathbf{u} \;=\; \text{Encode}(m) \;+\; \underbrace{\mathbf{e}^\top \mathbf{r} + e_2 - \mathbf{s}^\top \mathbf{e}_1}_{\displaystyle \delta} .$$

The encoded message, plus a leftover called the decryption error.

03.What $\delta$ looks like

Every ingredient of $\delta$ is small. The vectors $\mathbf{e}$, $\mathbf{r}$, $\mathbf{s}$ and $\mathbf{e}_1$ all came from a centred binomial distribution with $\eta \le 3$, so every coefficient is in $\{-3, \ldots, 3\}$, and $e_2$ is one more such polynomial.

So each coefficient of $\delta$ is a sum of products of small numbers, centred near zero. It is not zero, and it cannot be made zero, because the noise is what provides the security. The question is only whether it stays small enough.

04.The bound

Decoding returns the correct bit for coefficient $j$ exactly when $\delta_j$ has not pushed the coefficient past the midpoint between the two anchors $0$ and $\lceil q/2 \rceil$. That midpoint is a quarter of the way round, so the condition is

$$|\delta_j| \;<\; \frac{q}{4} \;=\; \frac{3329}{4} \;=\; 832.25 .$$

That single inequality is what every parameter in the scheme is calibrated against. Noise widths, module rank and compression widths all trade against this one number.

Two consequences follow immediately.

The bound is per coefficient. There are 256 of them in a message and each is an independent chance to fail, so the failure probability for a whole message is roughly 256 times the per-coefficient probability.

And the bound explains step E4. Encoding to $0$ and $\lceil q/2 \rceil$ puts the anchors as far apart as the ring allows, which makes the tolerance $q/4$ rather than something smaller. Any other encoding would leave less room.

05.Adding compression back

Compression is lossy, so Bob does not recover $\mathbf{u}$ and $v$ exactly. Write the rounding errors as $\mathbf{c}_u$ and $c_v$. Repeating the derivation with $\mathbf{u} + \mathbf{c}_u$ and $v + c_v$ gives

$$w \;=\; \text{Encode}(m) \;+\; \underbrace{\mathbf{e}^\top \mathbf{r} + e_2 - \mathbf{s}^\top \mathbf{e}_1 \;-\; \mathbf{s}^\top \mathbf{c}_u \;+\; c_v}_{\displaystyle \delta'} .$$

Two new terms, and their asymmetry is the reason $d_u$ and $d_v$ differ.

The term $-\mathbf{s}^\top \mathbf{c}_u$ is the compression noise on $\mathbf{u}$ multiplied by the secret. Multiplication inflates it, so $\mathbf{u}$ must be compressed gently. Hence $d_u = 10$.

The term $+c_v$ is the compression noise on $v$ standing alone, unmultiplied by anything. It enters the budget at full size and no larger, so $v$ can be compressed hard. Hence $d_v = 4$.

That is the whole justification for two different compression widths, and it comes straight out of this equation.

06.The published failure probabilities

Folding all the distributions through $\delta'$ and applying concentration bounds gives the numbers in FIPS 203:

$$< 2^{-139} \text{ at level 1}, \qquad < 2^{-164} \text{ at level 3}, \qquad < 2^{-174} \text{ at level 5}.$$

These deserve a sentence about what they mean, because a non-zero failure probability is unfamiliar to anyone whose intuition comes from RSA, where decryption either works or the key is wrong.

A probability of $2^{-139}$ is not "rare". It is smaller than the chance of guessing a 128-bit key correctly on the first try. No deployment will ever observe one.

The reason it has to be non-zero at all is that the noise is unbounded in principle. The centred binomial has finite support, so $\delta$ is actually bounded, but the bound is far above $q/4$ and only the extreme tail exceeds it. Parameters are chosen to push that tail below the point where anybody could exploit it.

That last clause matters. A decryption failure is not merely an inconvenience: an attacker who can induce failures learns something about $\mathbf{s}$, since whether a given ciphertext fails depends on the secret. Attacks of that form exist against schemes with sloppier margins. Pushing the probability below $2^{-139}$ makes finding even one failing ciphertext harder than breaking the scheme directly.