Exercises

01.1. Why the rejection seed must be secret and random

Argue why the implicit-rejection value $z$ has to live inside $sk$ and be uniformly random, rather than being, say, a hash of $pk$. What attack opens up if $z$ is predictable?

Answer. The whole point of implicit rejection in The Fujisaki-Okamoto Wrapper is that an attacker cannot tell an accepted ciphertext from a rejected one, because both return 32 pseudorandom bytes.

If $z$ were derived from $pk$, the attacker would know it, since $pk$ is public. They could then compute the rejection key $\textsf{KDF}(z \,\|\, H(c))$ themselves for any $c$ they send, compare it against the key the session actually uses, and learn whether their ciphertext was accepted.

That restores the decryption oracle the transform exists to remove. With it, the attacker submits perturbed ciphertexts, learns which ones decrypt correctly, and each answer constrains the secret, exactly the attack sketched in The KEM Contract.

So $z$ must be unpredictable to anybody without $sk$, which means uniformly random and stored privately. It must also be fixed per key, not per call, so that the same bad ciphertext always yields the same wrong key. A fresh random value each time would let an attacker detect rejection by sending the same ciphertext twice and seeing different answers.

02.2. The worst-case error bound

For ML-KEM-768, compute an upper bound on $\|\delta'\|_\infty$ assuming every centred binomial coefficient takes its extreme value and every compression error is maximal. Is it below $q/4 = 832$?

Answer. Take the terms of $\delta'$ from Why Decryption Works one at a time, with $k = 3$, $n = 256$, $\eta_1 = \eta_2 = 2$.

$\mathbf{e}^\top \mathbf{r}$: three ring products, each output coefficient a sum of $256$ terms bounded by $2 \times 2 = 4$. Bound $3 \times 256 \times 4 = 3072$.

$e_2$: a single coefficient, bound $2$.

$\mathbf{s}^\top \mathbf{e}_1$: same shape as the first, bound $3072$.

$\mathbf{s}^\top \mathbf{c}_u$: the compression error on $\mathbf{u}$ is bounded by $q/2^{d_u + 1} = 3329/2048 \approx 1.63$, and it is multiplied by $\mathbf{s}$, giving $3 \times 256 \times 2 \times 1.63 \approx 2497$.

$c_v$: alone, bounded by $q/2^{d_v+1} = 3329/32 \approx 104$.

Total: about $\mathbf{8747}$.

No, it is not below $832$. It exceeds $q/4$ by more than a factor of ten.

That is the answer, and it is the point of the exercise. The worst case fails, so correctness cannot be an absolute guarantee. It is probabilistic, and the published bound of $2^{-164}$ at this level is a statement about the far tail of a distribution rather than about a maximum.

Reaching $8747$ would require all $768$ coefficients of two independent secrets to simultaneously sit at their extremes with matching signs. Each such coefficient hits $\pm 2$ with probability $1/16$, so the event is astronomically unlikely, and the concentration bounds that produce $2^{-164}$ are the formalisation of that.

3. Why $d_u > d_v$

Answer. From the error equation, compression noise on $\mathbf{u}$ enters as $-\mathbf{s}^\top \mathbf{c}_u$, multiplied by the secret. That multiplication is a full ring product summing $256$ terms, so the noise is amplified by roughly $kn\eta$ before it reaches the budget.

Compression noise on $v$ enters as $+c_v$, alone. Nothing multiplies it.

The arithmetic in exercise 2 makes the ratio concrete: $\mathbf{c}_u$ is bounded by $1.63$ and contributes $2497$ to the budget, while $c_v$ is bounded by $104$ and contributes $104$. So $\mathbf{u}$ must be compressed gently at $d_u = 10$ and $v$ can be compressed hard at $d_v = 4$, and they still cost comparable amounts.

04.4. Complete the toy example

Answer. Fully worked in A Worked Toy Example. Key generation gives $t_0 = 3 + 7X + 14X^2 + 2X^3$ and $t_1 = 5X + 5X^2 + 11X^3$. Encryption gives $u_0 = 5 + 5X + X^2 + 15X^3$, $u_1 = 3 + 5X + 16X^2 + 4X^3$, and $v = 16 + 4X + 4X^2 + 11X^3$. Decryption gives $v - \mathbf{s}^\top\mathbf{u} = 9 + 16X + 16X^2 + 5X^3$, whose constant coefficient is exactly $9$, so the bit decodes as $1$.

The instructive part is the last coefficient, $5$, against a tolerance of $q/4 = 4.25$. That is a genuine decryption failure on a coefficient carrying no message, and it is what exercise 2's bound predicts at these parameters.

05.5. The cost of re-encryption

Count the extra ring multiplications decapsulation performs relative to a bare decryption, and speculate on why this is preferred over a MAC.

Answer. Bare decryption is one inner product $\mathbf{s}^\top\mathbf{u}$, so $k$ ring multiplications, three at ML-KEM-768.

Re-encryption repeats the whole encryption: $A^\top\mathbf{r}$ is $k^2 = 9$ products, plus $\mathbf{t}^\top\mathbf{r}$ is another $3$. So twelve extra, four times the cost of the decryption itself.

Why not a MAC instead? A MAC would need a key, and that key would have to be derived from something both parties share. Before decapsulation completes, they share nothing except the public key, which the attacker also has. So a MAC key would have to come from the very secret the ciphertext is establishing, which is circular.

Re-encryption avoids the circularity by checking the ciphertext against itself: it is valid exactly when it is the unique ciphertext that this message and this derived randomness produce. That check needs no shared secret, only determinism, which is why the transform makes encryption deterministic in the first place.

06.6. Confirm the sizes

Answer. For $k = 3$, $n = 256$, $d_u = 10$, $d_v = 4$:

$$\text{ciphertext} = \frac{3 \cdot 256 \cdot 10}{8} + \frac{256 \cdot 4}{8} = 960 + 128 = 1088 \text{ bytes},$$ $$\text{public key} = 32 + \frac{3 \cdot 256 \cdot 12}{8} = 32 + 1152 = 1184 \text{ bytes}.$$

Uncompressed the ciphertext would be $1152 + 384 = 1536$ bytes, so the compressed form is $1088/1536 \approx 70.8\%$ of it, a saving of just over $29\%$.

07.7. Why the transpose is essential

Answer. The cancellation in Why Decryption Works works because $\mathbf{t}^\top = \mathbf{s}^\top A^\top + \mathbf{e}^\top$, so substituting it produces a term $\mathbf{s}^\top A^\top \mathbf{r}$ that exactly matches the one arriving from $\mathbf{s}^\top\mathbf{u} = \mathbf{s}^\top A^\top \mathbf{r} + \mathbf{s}^\top\mathbf{e}_1$.

If encryption used $A$ instead of $A^\top$, then $\mathbf{u} = A\mathbf{r} + \mathbf{e}_1$ and decryption would compute $\mathbf{s}^\top A \mathbf{r}$, while the substitution still delivers $\mathbf{s}^\top A^\top \mathbf{r}$. Since $A$ is not symmetric, those are different values and nothing cancels.

What remains would be $\text{Encode}(m)$ plus $\mathbf{s}^\top(A^\top - A)\mathbf{r}$ plus the usual noise. That middle term involves a uniform matrix and is large, not small, so it swamps the message entirely and every coefficient decodes at random.

The failure mode is worth knowing because it is silent in the wrong way. Key generation succeeds, encryption succeeds, ciphertexts are the right size, and decryption returns uniformly random bits. Nothing errors.