Appendix D: Solutions for Chapter 12

These are worked solutions to the exercises in Chapter 12: ML-DSA (FIPS 204) from scratch. Compute-and-derive exercises get a worked answer; the more open-ended ones get an editorial note pointing at the reasoning rather than a single number.

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

Exercise 1

The expected number of trips through the abort loop is the reciprocal of the joint acceptance probability, and the two rejection tests are independent enough to multiply. Each coefficient of $\mathbf{z}$ is a mask coefficient (uniform over $2\gamma_1$ values) plus a fixed secret-dependent shift, and it is accepted when it lands in the smaller range of $2(\gamma_1 - \beta) - 1$ values, so the per-coefficient acceptance probability is about $1 - \beta/\gamma_1$. Over all $256\ell$ coefficients the whole vector passes with probability roughly $(1 - \beta/\gamma_1)^{256\ell}$, and the low-part test on $\mathbf{r}_0$ passes with probability roughly $(1 - \beta/\gamma_2)^{256k}$. At ML-DSA-65 those two factors are $0.620$ and $0.317$, so the joint acceptance is $0.196$ and the expected repetition count is $1/0.196 = 5.10$. FIPS 204 Table 1 gives the expected repetition count for ML-DSA-65 as $5.1$. The $4.25$ in the same row is ML-DSA-44 and the $3.85$ is ML-DSA-87 (National Institute of Standards and Technology, 2024). The estimate matches the table, and that agreement is not confirmation, because both come from the same incomplete count. Algorithm 7 aborts in two places, not one. Line 23 runs the two tests above; line 28 rejects again, after the hint is built, when $\|c\mathbf{t}_0\|_\infty \ge \gamma_2$ or the hint weight exceeds $\omega$. Table 1’s figures come from equation 5 of the Dilithium round-3 submission, which prices line 23 only (Bai et al., 2021). NIST’s potential-updates sheet for FIPS 204, last revised 31 July 2026, records the omission: the repetition numbers are not quite accurate, as a result of the overall failure rate for signing being affected by line 28 of Algorithm 7, which had not been taken into account prior. The corrected values are $4.36$, $5.14$, and $3.91$, and Table 3’s minimum allowable loop-iteration limit for internal signing moves with them, from $814$ to $821$. Those are potential corrections rather than an official change to the standard. Read $5.10$ as the value of the two-test model and $5.14$ as the value of the loop this package actually runs. The ratio says line 28 throws away about $0.8\%$ of the attempts line 23 accepted. That share is largest at ML-DSA-44, near $2.5\%$, because its $\gamma_2 = (q-1)/88$ is the narrowest of the three windows and $\|c\mathbf{t}_0\|_\infty < \gamma_2$ is correspondingly the tightest.

Signing $1{,}200$ distinct messages under one key with the deterministic $\text{rnd} = 0^{32}$ and averaging the traced iteration count gives a mean of $5.04$, which is inside sampling error of both the $5.10$ two-test estimate and the $5.14$ corrected figure. The shape of that sample carries more than its mean. The median is $4$ and the longest attempt run is $42$. Iteration counts are geometric, so the mean sits above the median and the tail is long, and a few hundred messages is not enough to pin the mean down: a $300$-message batch from the same key averaged $5.59$. Report the spread alongside the mean, or a sampling wobble reads as a disagreement with the standard.

Raising $\gamma_1$ makes the first factor closer to $1$, so fewer attempts are rejected and signing is faster, but it also widens the range each coefficient of $\mathbf{z}$ can take, so $\mathbf{z}$ packs at more bits per coefficient and the signature grows. ML-DSA-65 sits at $\gamma_1 = 2^{19}$, which packs $\mathbf{z}$ at $20$ bits per coefficient and holds the mean repetition count low enough that signing is fast in practice. The parameter is a direct time-versus-size lever, and FIPS 204 fixed it where the signature stays small without the loop running long.

Exercise 2

The four scalar cores are the ones the chapter prints and the ch12-mldsa package under solutions/ ships. The tests in tests/ch12/test_mldsa_rounding.py pin them. The interesting part is the edge. Inside the window $\|z\|_\infty \le \gamma_2$, adding $z$ to $r$ moves the Decompose high part by at most one step, because $z$ is smaller than the window width $2\gamma_2$ that separates adjacent high values, so a single bit (“did the high part change, and the sign of $r_0$ says in which direction”) is complete. One step past the window, at $\|z\|_\infty = \gamma_2 + 1$, the high part still moves by at most one step, but the direction can flip. A coefficient whose low part $r_0$ is small and positive sits just above its window center. A negative $z$ of magnitude $\gamma_2 + 1$ can push it down across the lower boundary, the opposite of the direction the sign of $r_0$ predicts. UseHint reads the positive $r_0$ and nudges the high part up by one, while the true high part moved down by one, so the recovered value is off by two. That two-unit gap, not a two-window jump, is what the single bit cannot represent.

A concrete counterexample at ML-DSA-65’s $\gamma_2 = 261888$:

Q = 8380417


def mod_pm(r, alpha):
    m = r % alpha
    return m - alpha if m > alpha // 2 else m


def decompose(r, gamma2):
    r %= Q
    r0 = mod_pm(r, 2 * gamma2)
    if r - r0 == Q - 1:
        return 0, r0 - 1
    return (r - r0) // (2 * gamma2), r0


def high_bits(r, gamma2):
    return decompose(r, gamma2)[0]


def make_hint(z, r, gamma2):
    return 1 if high_bits(r, gamma2) != high_bits((r + z) % Q, gamma2) else 0


def use_hint(h, r, gamma2):
    m = (Q - 1) // (2 * gamma2)
    r1, r0 = decompose(r, gamma2)
    if h == 1:
        return (r1 + 1) % m if r0 > 0 else (r1 - 1) % m
    return r1


gamma_2 = (Q - 1) // 32          # 261888
r, z = 3142657, -(gamma_2 + 1)   # |z| = gamma_2 + 1, one past the window
print("|z| =", abs(z), "= gamma_2 + 1 :", abs(z) == gamma_2 + 1)
print("UseHint(MakeHint(z, r), r) =", use_hint(make_hint(z, r, gamma_2), r, gamma_2))
print("HighBits(r + z)            =", high_bits((r + z) % Q, gamma_2))
# ==> |z| = 261889 = gamma_2 + 1 : True
# ==> UseHint(MakeHint(z, r), r) = 7
# ==> HighBits(r + z)            = 5

The recovered high value is $7$ where the true one is $5$, off by two. The true high part moved down one window ($6$ to $5$), but UseHint read the positive $r_0$ of the original $r$ and nudged up one window (to $7$). The coefficient crossed a single boundary, in the direction the sign of $r_0$ did not anticipate. This is why Sign’s second rejection test enforces $\|c\mathbf{t}_0\|_\infty < \gamma_2$. The hint corrects the perturbation $-c\mathbf{t}_0$, so that term has to stay strictly inside the window for the one-bit hint to be exact. An attempt where it does not is thrown away and resampled.

Exercise 3

Each tamper is caught by a different check, which is the point of the exercise. Corrupting a hint byte so a poly’s set positions are no longer strictly increasing is caught structurally: HintBitUnpack returns $\bot$ during signature decoding, and Verify returns false on the h is None guard before it computes anything. Flipping a byte inside the packed response $\mathbf{z}$ is caught one of two ways. If the flip pushes some coefficient past $\gamma_1 - \beta$, the norm test $\|\mathbf{z}\|_\infty < \gamma_1 - \beta$ rejects it. If the coefficient stays in range, the altered $\mathbf{z}$ changes the recomputed $\mathbf{w}'_{\text{approx}} = \mathbf{A}\mathbf{z} - c\mathbf{t}_1 2^d$, so the recomputed high bits and the recomputed challenge $\tilde c'$ no longer match $\tilde c$. Flipping a byte of the challenge hash $\tilde c$ makes SampleInBall produce a different challenge $c$, which changes $\mathbf{w}'_{\text{approx}}$ and therefore $\tilde c'$, so the comparison $\tilde c' = \tilde c$ fails.

No single check catches all three because they guard different layers. HintBitUnpack guards the wire format, rejecting a hint that is not a well-formed sparse encoding. The norm bound guards the size of the response, rejecting a $\mathbf{z}$ that is too large to have come from an honest signer. The challenge recomputation guards the Fiat-Shamir binding, rejecting any signature whose response, hint, and challenge are not mutually consistent under the hash. A forger has to defeat all three at once, and the three are checked against independent properties of the signature.

Exercise 4

The challenge is $\tilde c = H(\mu \mathbin\Vert \text{w1Encode}(\mathbf{w}_1), \lambda/4)$, and w1Encode packs each high-bit coefficient of $\mathbf{w}_1$ at $\text{w1\_bits}$ bits: $4$ for ML-DSA-65 and $6$ for ML-DSA-44. Changing the ML-DSA-65 width from $4$ to $6$ makes w1Encode emit a different, longer byte string for the same $\mathbf{w}_1$. Both results follow from where that string is used.

The round trip still verifies because Sign and Verify call the same w1Encode. Widening it in one place widens it on both sides, so the two hash the same bytes, derive the same $\tilde c$, and the comparison $\tilde c' = \tilde c$ holds. Nothing else in the scheme reads the width: the norm bound on $\mathbf{z}$, the hint decoding, and the recomputation of $\mathbf{w}_1'$ are all unaffected. A signer and verifier that agree on the wrong width agree, and the widened pair is a self-consistent signature scheme. What it is not is ML-DSA, and it interoperates with nothing that packs at $4$ bits.

The second case is that mismatch made explicit. A signer that packs at $6$ bits against a verifier that still packs at $4$, or the reverse, hash different inputs into $H$, so they derive different challenge hashes, and the comparison $\tilde c' = \tilde c$ fails on every signature. Only one side has to change for this: interoperability with the standardized encoding is lost the moment the two widths differ.

The lesson is that the byte layout is inside the security contract, not a free implementation choice. The Fiat-Shamir challenge commits to the exact encoded bytes of the commitment, so any two implementations that hope to interoperate must serialize $\mathbf{w}_1$ identically down to the bit width. This is the same reason FIPS 204 fixes every packing width in the §7.2 encoders (Algorithms 22 through 28) rather than leaving it to the implementer: a width mismatch is not a cosmetic difference, it is a different signature scheme that happens to share the same key. The w1_bits helper in the ch12-mldsa package carries its own test for exactly this reason, because getting it wrong corrupts $\tilde c$ silently rather than raising an error.

References

Bai, S., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1). NIST Post-Quantum Cryptography Project, Round 3 submission package. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

National Institute of Standards and Technology. (2024). FIPS 204: Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.204