Appendix D: Solutions for Chapter 11

This page collects solutions and editorial notes for the exercises in Chapter 11: ML-KEM (FIPS 203) from scratch. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the mlkem package under solutions/ch11-mlkem. From a clone of the companion repository, pytest tests/ch11 runs its suite. Appendix C has the setup.

Exercise 1

The compression operation $\mathrm{Compress}_d(x) = \lfloor (2^d / q) x \rceil \bmod 2^d$ followed by the matching decompression introduces rounding error bounded by $\lceil q / 2^{d+1} \rceil$. With $q = 3329$:

• $d = 10$: $\lceil 3329 / 2048 \rceil = 2$.
• $d = 11$: $\lceil 3329 / 4096 \rceil = 1$.
• $d = 4$: $\lceil 3329 / 32 \rceil = 105$.

ML-KEM-768 picks $(d_u, d_v) = (10, 4)$, so the compression error per coefficient is at most 2 in $\mathbf{u}$ and at most 105 in $v$. The asymmetry is deliberate, and the reason is where each error lands in the decryption identity rather than how many coefficients it covers. The term $\delta_v$ reaches the decoder bare, so 105 against a decoding half-width of $\lfloor q/4 \rfloor = 832$ is cheap. The term $\delta_u$ reaches it as $-\mathbf{s}^\top \delta_u$, a signed sum of $k n = 768$ products with secret coefficients, so it has to start far smaller.

Sweeping every $x \in \mathbb{Z}_q$ alongside the closed form shows the two agree at $d = 10$ and $d = 11$ but not at $d = 4$.

import math

q = 3329


def compress(x, d):
    return ((x * 2 ** d) + q // 2) // q % 2 ** d


def decompress(y, d):
    return ((q * y) + 2 ** (d - 1)) // 2 ** d


def sym(z):
    z %= q
    return z - q if z > q // 2 else z


for d in (10, 11, 4):
    bound = math.ceil(q / 2 ** (d + 1))
    worst = max(abs(sym(decompress(compress(x, d), d) - x)) for x in range(q))
    print(d, bound, worst)
# ==> 10 2 2
# ==> 11 1 1
# ==> 4 105 104

The closed form is an upper bound rather than the exact maximum because the $2^d$ decompression points are themselves integers. $\mathrm{Decompress}_d$ rounds $q y / 2^d$ to the nearest integer, so consecutive points sit $\lfloor q/2^d \rfloor$ or $\lceil q/2^d \rceil$ apart rather than exactly $q/2^d$ apart. Since $x$ is an integer too, the worst round-trip error is $\lfloor g/2 \rfloor$ for the widest gap $g$, while the closed form is $\lceil g/2 \rceil$. The two agree exactly when $g$ is even. At $d = 4$ the gaps are 208 and 209, giving $\lfloor 209/2 \rfloor = 104$ against a bound of 105; at $d = 10$ they are 3 and 4, giving $\lfloor 4/2 \rfloor = 2$, which is the bound. The same arithmetic at $d = 1$ gives gaps 1664 and 1665 and a true maximum of 832, which is the chapter’s $\lfloor q/4 \rfloor$ decoding half-width.

Exercise 2

The centered binomial $\mathrm{CBD}_\eta$ at $\eta = 2$ produces values in $\{-2, -1, 0, 1, 2\}$ with the binomial probabilities $\binom{4}{k+2} / 16$, so $0$ has probability $6/16$ and $\pm 2$ each have probability $1/16$. The uniform distribution over the same range has every value at probability $1/5$. The decryption-failure analysis depends on the variance and tail of the noise after polynomial multiplication. CBD has variance $\eta/2 = 1$ at $\eta = 2$; uniform on $\{-2, \ldots, 2\}$ has variance $\sum k^2 / 5 = 2$, twice as large.

The replacement sampler is a few lines, and the variance ratio is the number to have in hand before running anything.

import numpy as np

Q = 3329


def sample_poly_uniform(eta, seed, nonce):
    """Drop-in for sample_poly_cbd: flat on {-eta, ..., eta}."""
    rng = np.random.default_rng(int.from_bytes(seed[:8], "little") ^ nonce)
    return rng.integers(-eta, eta + 1, size=256, dtype=np.int64) % Q


def cbd_variance(eta):
    return eta / 2


def uniform_variance(eta):
    return ((2 * eta + 1) ** 2 - 1) / 12


for eta in (2, 3):
    print(eta, cbd_variance(eta), uniform_variance(eta))

f = sample_poly_uniform(3, b"\x00" * 32, 0)
sym = [int(x) - Q if int(x) > Q // 2 else int(x) for x in f]
print(sorted(set(sym)))
# ==> 2 1.0 2.0
# ==> 3 1.5 4.0
# ==> [-3, -2, -1, 0, 1, 2, 3]

Set $(d_u, d_v) = (8, 4)$ and $(\eta_1, \eta_2) = (3, 2)$, leaving everything else at ML-KEM-768. Over $10^4$ K-PKE round trips, the centered binomial fails 0 times and the uniform sampler fails 2,840, a rate of $28.4\%$. The budget still absorbs $\mathrm{CBD}_3$ completely at these widths, so the whole difference is attributable to the distribution rather than to the narrowed budget.

The usable window is narrower than it looks. At the real $(10, 4)$ neither sampler fails once in $10^4$ trials, and at $(6, 3)$ both fail on essentially every trial, because the budget is gone outright and the distribution no longer matters. The comparison only exists in between.

The mechanism is the heavier tail. At $\eta = 3$ the centered binomial puts $1/64$ on each of $\pm 3$ where uniform puts $1/7$, about nine times as much. The terms do not all scale alike. Each coefficient of $\mathbf{e}^\top \mathbf{y}$ is a signed sum of $k n = 768$ products of two resampled values, and for independent centered factors the variance of a product is the product of the variances, so that term grows by $(8/3)^2 = 64/9$. The term $\mathbf{s}^\top \mathbf{e}_1$ pairs an $\eta_1$ factor with an $\eta_2$ factor and grows by $(8/3) \cdot 2 = 16/3$. The bare $e_2$ doubles. The compression term $\mathbf{s}^\top \delta_u$, which at $d_u = 8$ carries about $70\%$ of the centered-binomial total, grows by exactly $8/3$ because only $\mathbf{s}$ is resampled, and $\delta_v$ does not change. Weighted together, the standard deviation of the decoder input grows from about $150$ to about $255$, a factor of $1.7$, against a fixed decoding half-width of $\lfloor q/4 \rfloor = 832$. Under a normal approximation that moves the per-coefficient overflow probability from about $3 \times 10^{-8}$ to about $1.1 \times 10^{-3}$, and spread over 256 coordinates the second figure is a failure rate near $25\%$, which is what the measured $28.4\%$ reflects.

Exercise 3

Decapsulation of a tampered ciphertext $c^*$ fails the FO re-encryption check, so the implicit-rejection branch fires and the returned shared secret is the rejection value $\bar{K} = J(z \mathbin\Vert c^*)$, where $z$ is the per-key rejection seed stored in $\text{dk}$. The argument to $J$ is the ciphertext as submitted, not the re-encryption $c'$ the decapsulator computed and rejected. FIPS 203 Algorithm 18 fixes $\bar{K} \leftarrow J(z \mathbin\Vert c)$ at step 7, before the comparison. Each distinct $c^*$ gives a distinct $\bar{K}$ as far as any attacker can tell, since finding two ciphertexts with the same rejection value is a collision on $J$.

The property that blocks the decryption oracle is a different one. $J(z \mathbin\Vert \cdot)$ is indistinguishable from a random function to anyone who does not hold $z$, so the returned value has no algebraic dependence on the K-PKE secret $\mathbf{s}$. An attacker who submits malformed ciphertexts therefore learns a random function of their own inputs, and nothing about whether the malformation hit the decoding band, the re-encryption check, or anything else.

Exercise 4

The two approaches are equivalent by the definition of matrix transpose: indexing the transposed matrix at $(i, j)$ returns the same value as indexing the original at $(j, i)$. The transpose=True flag in sample_matrix_ntt is purely an indexing convention: it produces a matrix whose $(i, j)$ entry is what the non-transposed call would produce at $(j, i)$, derived from the same XOF stream. The pytest is a one-liner that builds both and asserts elementwise equality of the resulting u_hat tensors after the inner-product loop.

The exercise reinforces that FIPS 203 samples one matrix from the public seed $\rho$ and uses it in two orientations. K-PKE.KeyGen takes it un-transposed, as $\hat{\mathbf{t}} = \hat{\mathbf{A}} \circ \hat{\mathbf{s}} + \hat{\mathbf{e}}$ at Algorithm 13 line 18. K-PKE.Encrypt takes it transposed, as $\mathbf{u} = \text{NTT}^{-1}(\hat{\mathbf{A}}^\top \circ \hat{\mathbf{y}}) + \mathbf{e}_1$ at Algorithm 14 line 19. That pairing is what makes $\mathbf{s}^\top \mathbf{u}$ reduce to $(\mathbf{A}\mathbf{s})^\top \mathbf{y}$ plus small terms, which is $\mathbf{t}^\top \mathbf{y}$ plus small terms, which is what cancels against $v$. K-PKE.Decrypt (Algorithm 15) touches no matrix at all. The only matrix work inside Decaps happens in its re-encryption, and that is K-PKE.Encrypt, so it is transposed too.