Exercises

01.1. Prove that rejection sampling removes the shift

With $y$ uniform on $(-\gamma, \gamma]$, $|s| \le \beta$, $z = y + s$, and acceptance when $|z| < \gamma - \beta$, prove that the accepted $z$ is uniform on $(-\gamma+\beta,\; \gamma-\beta]$ independent of $s$.

Answer. Before conditioning, $z$ is uniform on the shifted interval $(-\gamma + s,\; \gamma + s]$, which has width $2\gamma$ and so has density $1/(2\gamma)$ at every point inside it.

Call the acceptance region $S = (-\gamma+\beta,\; \gamma-\beta]$.

The key step is that $S \subseteq (-\gamma+s,\; \gamma+s]$ for every admissible $s$. The left endpoint needs $-\gamma + s \le -\gamma + \beta$, which holds because $s \le \beta$. The right endpoint needs $\gamma - \beta \le \gamma + s$, which holds because $s \ge -\beta$. So $S$ sits inside the shifted interval no matter what $s$ is.

Therefore the density of $z$ is the constant $1/(2\gamma)$ at every point of $S$, regardless of $s$. Conditioning on $z \in S$ renormalises that constant over $S$, giving the uniform distribution on $S$ with density $1/(2(\gamma - \beta))$.

The result mentions $\gamma$ and $\beta$ only, both public. So the accepted values carry no information about $s$, which is the property the security proof needs.

Note what would break it. If $|s|$ could exceed $\beta$, then $S$ would poke outside the shifted interval on one side, that part would have density zero, and the shift would be visible again. The bound $\beta$ is therefore not a convenience but a correctness condition, which is why $\beta = \tau\eta$ is derived rather than chosen.

02.2. Acceptance rate for ML-DSA-65

Estimate the per-attempt acceptance probability for $\gamma_1 = 2^{19}$, $\beta = 196$, $\ell = 5$, $n = 256$, assuming coefficients are independent. What is the expected number of restarts?

Answer. Per coefficient,

$$1 - \frac{\beta}{\gamma_1} \;=\; 1 - \frac{196}{524288} \;=\; 0.999626 .$$

There are $\ell \cdot n = 5 \times 256 = 1280$ coefficients in $\mathbf{z}$, so the joint probability is

$$0.999626^{1280} \;\approx\; 0.62 ,$$

giving about $1/0.62 \approx 1.6$ attempts expected.

That is the bound from the $\mathbf{z}$ check alone. The real rate is lower because Signing applies two further rejection tests, on the low bits and on the hint weight, and all must pass together. Those bring the true figure into the four-to-six range quoted in Rejection Sampling, or Fiat-Shamir With Aborts.

The exercise is worth doing precisely because the naive estimate is optimistic. The dominant cost comes from the checks that exist for verification reasons rather than for secrecy.

03.3. Attack the version without rejection

Answer. Collect many pairs $(\mathbf{z}^{(i)}, c^{(i)})$ and exploit that $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$ with $\mathbf{y}$ symmetric about zero.

Since $\mathbb{E}[\mathbf{y}] = 0$, taking expectations gives $\mathbb{E}[\mathbf{z} \mid c] = c\,\mathbf{s}_1$. So averaging the released responses grouped by challenge estimates $c\mathbf{s}_1$ directly, and dividing out the known $c$ recovers $\mathbf{s}_1$.

More practically, an attacker computes $\sum_i c^{(i)-1}\mathbf{z}^{(i)}$ over many signatures. The $\mathbf{y}$ contributions are independent and mean-zero so they average towards nothing, while the $\mathbf{s}_1$ contribution is the same every time and accumulates linearly. The signal-to-noise ratio grows like $\sqrt{N}$, so a few thousand signatures suffice.

Why the Naive Version Leaks runs the one-coordinate version: 400,000 samples recover a secret of $3$ as $3.151$, and with rejection the same estimator returns $0.120$.

4. Toy key generation over $\mathbb{F}_{97}$

Answer. With $d = 4$, decomposing $\mathbf{t} = 2^4 \mathbf{t}_1 + \mathbf{t}_0$ means splitting each coefficient into a multiple of $16$ plus a remainder centred on zero, so $\mathbf{t}_0 \in (-8, 8]$ and therefore $\|\mathbf{t}_0\|_\infty \le 8 = 2^{d-1}$, as required.

Concretely, a coefficient of $53$ decomposes as $53 = 3 \times 16 + 5$, giving $t_1 = 3$ and $t_0 = 5$. A coefficient of $61$ gives $61 = 4 \times 16 - 3$, so $t_1 = 4$ and $t_0 = -3$, taking the nearest multiple rather than rounding down. That centring is what keeps $|t_0| \le 8$ rather than $\le 15$, and it halves the perturbation the hint has to cover.

05.5. Which assumption protects what

Answer. Module-LWE protects the key. The public key is $\mathbf{t} = A\mathbf{s}_1 + \mathbf{s}_2$, exactly a Module-LWE sample, so recovering $\mathbf{s}_1$ from $pk$ alone is Module-LWE.

Module-SIS prevents forgery. Two valid signatures on one message under one challenge, subtracted, cancel the message-dependent parts and leave a short non-zero element of the kernel of $[A \| I_k]$, which is a Module-SIS solution. So forging implies solving it.

The division matters because the two cover different attackers, as Security, and the Chapter Summary describes: Module-LWE covers someone with only the public key, Module-SIS covers someone who also holds unlimited signatures. Rejection sampling is the bridge, because it makes signatures simulatable and so reduces the second attacker to the first.

06.6. Bound the challenge product

Show $\|c\mathbf{s}_1\|_\infty \le \tau\eta$ and identify the worst case.

Answer. Each coefficient of the product $c \mathbf{s}_1$ in $R_q$ is a sum of terms $c_i \cdot s_j$ where the indices combine to the output position, with a sign flip from $X^n = -1$ where they wrap.

Only $\tau$ of the $c_i$ are non-zero, and each is $\pm 1$. So the sum has at most $\tau$ non-zero terms, each of absolute value at most $|s_j| \le \eta$. Hence

$$\|c\mathbf{s}_1\|_\infty \;\le\; \tau \cdot 1 \cdot \eta \;=\; \tau\eta \;=\; \beta .$$

Equality needs all $\tau$ terms landing on the same output coefficient to have the same sign after the negacyclic flip, and every corresponding $s_j$ to be at its extreme $\pm\eta$. That is an alignment of $\tau$ independent choices, so it essentially never occurs, and the real distribution of $\|c\mathbf{s}_1\|_\infty$ sits far below $\beta$.

Using the worst case anyway is deliberate. The rejection rule has to be safe for every possible secret, not for a typical one, or the argument in exercise 1 fails.

07.7. Why the loop reseeds deterministically

Answer. Each attempt needs a fresh $\mathbf{y}$, and the obvious way is to draw new randomness every time. ML-DSA instead derives $\mathbf{y}$ deterministically from the key salt $K$, the message digest, and a counter that increments per attempt.

The reason is fault and randomness robustness. If the platform's randomness source is weak or repeats, a fresh-randomness signer could produce two different signatures on the same message with the same $\mathbf{y}$, and subtracting them recovers $c\mathbf{s}_1$ for two different challenges, which gives $\mathbf{s}_1$. That is precisely the failure that broke the PlayStation 3's ECDSA implementation, mentioned in What a Signature Is.

Deriving $\mathbf{y}$ from a counter makes repetition impossible without repeating the counter, which the signer controls. It also makes signing deterministic and therefore testable against fixed vectors, which matters for a standard.

An attacker watching many restarts learns the number of attempts, which is public, and nothing else. The values that failed are discarded and never released, and the counter is not secret.