A Worked Toy Example

At the real parameters nothing can be checked by hand. This note shrinks every dimension until the whole scheme fits on a page, and runs it.

Fix the ring to $\mathcal{R}_{17}$ with $n = 4$, module rank $k = 2$, and errors drawn from $\{-1, 0, 1\}$. The message is a single bit. Every product below is in $\mathcal{R}_{17}$, meaning reduce with $X^4 = -1$ and then modulo $17$.

01.Key generation

Take

$$A = \begin{pmatrix} 3 + X & 2 + 4X^2 \\ X + 2X^2 & 5 + 3X^3 \end{pmatrix}, \quad \mathbf{s} = \begin{pmatrix} 1 - X^2 \\ X - X^3 \end{pmatrix}, \quad \mathbf{e} = \begin{pmatrix} X^3 \\ 1 - X \end{pmatrix} .$$

Compute $\mathbf{t} = A\mathbf{s} + \mathbf{e}$. Working the first component, $(3+X)(1-X^2) + (2+4X^2)(X-X^3) + X^3$:

The first product is $3 + X - 3X^2 - X^3$.

The second is $2X - 2X^3 + 4X^3 - 4X^5$. The $X^5$ term reduces: $X^5 = X \cdot X^4 = -X$, so $-4X^5 = +4X$. That gives $6X + 2X^3$.

Adding those and the error $X^3$:

$$t_0 \;=\; 3 + 7X - 3X^2 + 2X^3 \;\equiv\; 3 + 7X + 14X^2 + 2X^3 \pmod{17},$$

using $-3 \equiv 14$.

The same procedure on the second row gives

$$t_1 \;=\; 5X + 5X^2 + 11X^3 .$$

So the public key is $(A, \mathbf{t})$ and the secret key is $\mathbf{s}$.

02.Encryption

Encrypt the bit $m = 1$. It encodes to $\lceil 17/2 \rceil = 9$ in the constant coefficient, so $\text{Encode}(m) = 9$.

Take

$$\mathbf{r} = \begin{pmatrix} 1 + X \\ -X^2 \end{pmatrix}, \qquad \mathbf{e}_1 = \begin{pmatrix} X - X^3 \\ 1 \end{pmatrix}, \qquad e_2 = 1 .$$

Compute $\mathbf{u} = A^\top \mathbf{r} + \mathbf{e}_1$, remembering the transpose, so the first component uses the first column of $A$:

$$u_0 \;=\; 5 + 5X + X^2 + 15X^3, \qquad u_1 \;=\; 3 + 5X + 16X^2 + 4X^3 .$$

Compute $v = \mathbf{t}^\top \mathbf{r} + e_2 + 9$:

$$v \;=\; 16 + 4X + 4X^2 + 11X^3 .$$

The ciphertext is $(\mathbf{u}, v)$. No compression in this toy version.

03.Decryption

Bob computes $\mathbf{s}^\top \mathbf{u} = s_0 u_0 + s_1 u_1$, which comes to

$$\mathbf{s}^\top \mathbf{u} \;=\; 7 + 5X + 5X^2 + 6X^3 ,$$

and then

$$w \;=\; v - \mathbf{s}^\top \mathbf{u} \;=\; (16-7) + (4-5)X + (4-5)X^2 + (11-6)X^3 \;=\; 9 + 16X + 16X^2 + 5X^3 ,$$

reducing $-1 \equiv 16$.

The constant coefficient is $9$. Encode put $9$ there for a $1$ bit and $0$ for a $0$ bit, so the distance to $9$ is zero and the distance to $0$ is eight. The nearer anchor is $9$.

Decoded bit: $m = 1$. Correct.

04.Checking the error equation

Why Decryption Works claimed that $w = \text{Encode}(m) + \delta$ with $\delta = \mathbf{e}^\top \mathbf{r} + e_2 - \mathbf{s}^\top \mathbf{e}_1$. Verify it directly on these numbers.

Computing that expression gives

$$\delta \;=\; 0 + 16X + 16X^2 + 5X^3 ,$$

whose coefficients written in centred form, taking values above $8$ as negative, are

$$\delta \;=\; (0,\; -1,\; -1,\; 5) .$$

And indeed

$$\text{Encode}(m) + \delta \;=\; 9 + 0 + 16X + 16X^2 + 5X^3 \;=\; w . \qquad\checkmark$$

The cancellation happened exactly as the algebra promised, on real numbers, with no approximation.

05.The interesting part: a decryption failure

Look at the last coefficient of $\delta$. It is $5$.

The tolerance from Why Decryption Works is $|\delta_j| < q/4$, and here

$$\frac{q}{4} \;=\; \frac{17}{4} \;=\; 4.25 .$$

So $|\delta_3| = 5 > 4.25$. That coefficient has broken the bound.

Trace the consequence. The message occupied only the constant coefficient, so coefficient 3 of $\text{Encode}(m)$ is $0$ and should decode to a $0$ bit. But $w_3 = 5$, and on the circle modulo $17$ the distance from $5$ to the anchor $9$ is $4$, while the distance to the anchor $0$ is $5$. The nearer anchor is $9$, so it decodes to $1$.

Wrong. Had the message been four bits rather than one, this instance would have decrypted three of them correctly and the fourth incorrectly.

This is a genuine decryption failure, produced by honest parties following the protocol exactly. Nobody cheated and nothing was mis-computed.

It happens because $q = 17$ leaves a tolerance of $4.25$, and errors that are sums of several products of values in $\{-1, 0, 1\}$ reach $5$ without difficulty. The toy parameters have essentially no margin.

Compare the real ones. At $q = 3329$ the tolerance is $832.25$, and the noise is a sum of products of centred binomial values with $\eta \le 3$ over $256$ coefficients. Reaching $832$ requires the far tail of that distribution, which is why the published failure probability is below $2^{-139}$.

So the toy example demonstrates two things at once: that the algebra works, and that the parameters are what make it usable. Shrinking $q$ for legibility broke the scheme, which is the most direct available evidence that the real values were chosen rather than picked.

06.Chapter summary

ML-KEM is Module-LWE with the sharp edges removed.

The narrow job is establishing a shared symmetric key over an open channel, and the KEM formulation returns the key rather than accepting one, which keeps user data out of the public-key primitive and makes the security analysis tractable.

The construction has two layers. The inner one is a public-key encryption scheme where key generation publishes $\mathbf{t} = A\mathbf{s} + \mathbf{e}$ and keeps $\mathbf{s}$, encryption sends $\mathbf{u} = A^\top\mathbf{r} + \mathbf{e}_1$ alongside $v = \mathbf{t}^\top\mathbf{r} + e_2 + \text{Encode}(m)$, and decryption computes $v - \mathbf{s}^\top\mathbf{u}$. The term $\mathbf{s}^\top A^\top \mathbf{r}$ appears twice with opposite signs and cancels, which is the whole construction, and the transpose in encryption exists precisely to make it happen.

What survives the cancellation is the encoded message plus a small error $\delta$. Decoding is correct exactly when $|\delta_j| < q/4$ for every coefficient, and every parameter in the scheme is calibrated against that inequality. Encoding a bit to $0$ or $\lceil q/2 \rceil$ maximises the tolerance. Compression widths differ because the noise on $\mathbf{u}$ arrives multiplied by the secret while the noise on $v$ arrives alone.

The outer layer is the Fujisaki-Okamoto transform, which makes encryption deterministic in the message, verifies ciphertexts by re-encrypting them, and returns a pseudorandom dummy key on mismatch rather than an error. That implicit rejection is what defeats an active attacker, and it costs a full extra encryption on every decapsulation.

Every random value the scheme needs comes from Keccak in one parameterisation or another, so one hash engine serves the whole design.

Three parameter sets share $n = 256$ and $q = 3329$ and differ only in module rank and noise widths, so one arithmetic datapath serves all of them. ML-KEM-768 is the recommended default, at 1184-byte public keys and 1088-byte ciphertexts.

The next chapter builds ML-DSA, which solves the other half of the problem. Encryption protects secrecy. Signatures protect authenticity, and the same lattice machinery does both.