Appendix D: Solutions for Chapter 10

This page collects solutions and editorial notes for the exercises in Chapter 10: Regev encryption 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 regev_pke package under solutions/ch10-regev-pke. From a clone of the companion repository, pytest tests/ch10 runs its suite. Appendix C has the setup.

Exercise 1

Take $r \in \{0, 1\}^m$ uniform and $e \in \{-1, 0, 1\}^m$ uniform at $(m = 8, B = 1)$. The noise term $e^\top r$ is then a sum of up to $m$ products, each in $\{-1, 0, 1\}$, so it is supported on $\{-8, \ldots, 8\}$.

At $q = 13$ the decoder’s two codewords are $0$ and $\lfloor q/2 \rfloor = 6$, and its regions have different widths. It returns $0$ on the seven residues $\{0, 1, 2, 3\} \cup \{10, 11, 12\}$ and $1$ on the six residues $\{4, \ldots, 9\}$. The bit $0$ therefore survives $\lvert e^\top r \rvert \leq 3$, while the bit $1$ survives only $-2 \leq e^\top r \leq 3$. At $e^\top r = -3$ the decrypted value under the bit $1$ is $6 - 3 = 3$, which the decoder reads as $0$.

Enumerating all $3^8 \cdot 2^8 = 1{,}679{,}616$ pairs $(e, r)$ gives $\Pr[\text{fail} \mid \mu = 0] = 0.02969$ and $\Pr[\text{fail} \mid \mu = 1] = 0.07490$. Averaged over the two message bits the exact rate is $0.05229$, which is the figure the chapter quotes as about $5\%$. Reading the failure condition as the symmetric $\lvert e^\top r \rvert > 3$ for both bits gives $0.02969$ instead, understating the true rate by a factor of about $1.8$.

Over 1000 seeds with both bits encrypted the sample is 2000 trials, so the standard error is $\sqrt{p(1-p)/2000} \approx 0.005$. An observed rate outside roughly 4 to 6 percent points at a bug rather than at sampling noise.

Exercise 2

Each single-bit ciphertext is $(c_1, c_2) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$, which is $n + 1$ entries in $\mathbb{Z}_q$. Encrypting $k$ bits independently produces $k$ ciphertexts of $n + 1$ entries each, for a total of $k(n + 1)$ entries to deliver $k$ bits. The expansion factor is $n + 1$ entries in $\mathbb{Z}_q$ per plaintext bit. At $n = 4$ this is 5, and at ML-KEM-style $n = 768$ it would be 769 (which is why ML-KEM packs 256 message bits into one Module-LWE ciphertext rather than running 256 independent flat ciphertexts).

Exercise 3: noise budget under signed randomness

The single-bit Regev decryption error is

$$e^\top r = \sum_{i=1}^{m} e_i r_i,$$

with each $e_i \in \{-B, \ldots, B\}$ and each $r_i$ now in $\{-1, 0, 1\}$ instead of $\{0, 1\}$.

Worst-case bound. Each product $e_i r_i$ is in $\{-B, \ldots, B\}$ regardless of which sign bag $r_i$ is drawn from, because $\lvert r_i \rvert \le 1$ in both cases. The triangle inequality gives

$$\lvert e^\top r \rvert \le \sum_{i=1}^{m} \lvert e_i r_i \rvert \le \sum_{i=1}^{m} \lvert e_i \rvert \cdot \lvert r_i \rvert \le m B.$$

So the worst-case bound is unchanged at $m B$.

Typical magnitude. What changes is the variance of $e^\top r$ under the random sampling. With $r_i \in \{0, 1\}$ uniform, $\Pr[r_i = 1] = 1/2$, so $\mathbb{E}[r_i] = 1/2$ and $\mathrm{Var}(r_i) = 1/4$. With $r_i \in \{-1, 0, 1\}$ uniform, $\mathbb{E}[r_i] = 0$ and $\mathbb{E}[r_i^2] = 2/3$, so $\mathrm{Var}(r_i) = 2/3$.

Treating $e_i$ as independent zero-mean with variance $\mathrm{Var}(e_i) = \sigma_e^2$, the sum $e^\top r$ has variance

$$\mathrm{Var}(e^\top r) = \sum_i \mathbb{E}[e_i^2 r_i^2] = m \sigma_e^2 \cdot \mathbb{E}[r_i^2].$$

For $r \in \{0, 1\}^m$: $\mathbb{E}[r_i^2] = 1/2$, so $\mathrm{Var}(e^\top r) = m \sigma_e^2 / 2$ and the typical magnitude is $\sqrt{m/2} \cdot \sigma_e$.

For $r \in \{-1, 0, 1\}^m$: $\mathbb{E}[r_i^2] = 2/3$, so $\mathrm{Var}(e^\top r) = 2 m \sigma_e^2 / 3$ and the typical magnitude is $\sqrt{2m/3} \cdot \sigma_e$.

The ratio is $\sqrt{(2/3) / (1/2)} = \sqrt{4/3} \approx 1.15$, so signed randomness inflates the typical noise magnitude by about 15%. The worst case is unchanged, but the average failure probability rises slightly because the noise distribution is wider.

import math
print(round(math.sqrt(4 / 3), 3))
# ==> 1.155

The practical implication: schemes that use signed randomness (like ML-KEM’s centered binomial distribution, which produces signed values) need a slightly wider decoding band or slightly tighter noise bound than schemes using $\{0, 1\}$-valued randomness, all else equal.

ML-KEM does not answer that by narrowing the distribution. Its encryption randomness comes from $\mathrm{CBD}_{\eta_1}$, with $\eta_1 = 3$ at ML-KEM-512 and $\eta_1 = 2$ at the other two parameter sets, and $\mathrm{CBD}_\eta$ has second moment $\eta/2$ (National Institute of Standards and Technology, 2024). That is $1.5$ or $1.0$, above both the $\{0, 1\}$-uniform $1/2$ and the ternary $2/3$. The room comes from the modulus instead. ML-KEM encodes one message bit per coefficient of $\mathbb{Z}_q$ at $q = 3329$, so its decoder has a radius of $\lfloor q/2 \rfloor / 2 = 832$, against the $3$ this chapter’s $q = 13$ toy works with.

Exercise 4

The encoding shift $\lfloor q/2 \rfloor$ places bit 0 near 0 and bit 1 near $q/2$ in $\mathbb{Z}_q$, with each band $q/4$ wide on each side, so the decoder must distinguish noise of magnitude up to $q/4$. Shifting bit 1 to $\lfloor q/3 \rfloor$ instead puts the two encoding centers at distance $q/3$ apart. The decoder now splits into bit 0 (around 0) and bit 1 (around $q/3$), and on the cycle $\mathbb{Z}_q$ it has two boundaries rather than one. They are the midpoint of the short arc between the codewords, at $q/6$, and the midpoint of the long arc, at $2q/3$. Each codeword sits $q/6$ from the first boundary and $q/3$ from the second, so the first is the binding one. The noise bound that still decodes correctly drops to $\lvert e^\top r \rvert < q/6$, two thirds of the original $q/4$ at the same $q$.

References

National Institute of Standards and Technology. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.203