| \(P_{\mathrm{norm}}\) | Equation (5) | Overstatement | |
|---|---|---|---|
| ML-DSA Variant | |||
| ML-DSA-44 | 0.23272 | 0.23502 | 1.0% |
| ML-DSA-65 | 0.19539 | 0.19631 | 0.5% |
| ML-DSA-87 | 0.25809 | 0.25961 | 0.6% |
The Rejection Rate of ML-DSA Signing: Correcting FIPS-204
Cryptography
Introduction
FIPS-204 Table 1 provides the expected number of iterations of the ML-DSA signing loop. Appendix C of the same document uses those figures to derive a loop bound for implementations that choose to impose one. Measurement says the true iteration counts are closer to 4.36, 5.14 and 3.91. The discrepancy is small, but it is not noise, and it is not a rounding artefact. It is a scoping error that happened in translation from the CRYSTALS-Dilithium specification into the standard, and it propagates into every performance figure derived from Table 1 - expected latency, energy budgets, percentile planning, and the loop bound itself.
This post works through where the error comes from and computes the correct values from first principles. The short version:
- The figures in FIPS-204 Table 1 account for one of the two rejection points in the signing loop.
- The missing one is a consequence of public-key compression, not of security. That is plausibly why a number computed for the security analysis was reused as a performance number.
- Correcting it changes the expected iteration counts by 1-2%, and moves the Appendix C loop bound from 814 to 820.
Nothing here affects the security of ML-DSA. The rejection sampling still does what the security proof needs it to do; only the published cost of it is wrong.
This post is the companion analysis referenced from the IETF draft Adapting Constrained Devices for Post-Quantum Cryptography, and supplies the numbers used in Benchmarking ML-DSA Signature Generation.
NoteCredit
The discrepancy was first reported on pqc-forum by Hanno Böck, with analysis from Markku-Juhani Saarinen, and had been observed earlier in measurements by Mike Hamburg and colleagues in March 2024. This post is an independent derivation that arrives at the same values.
Where the Loop Actually Rejects
ML-DSA is built on Fiat-Shamir with Aborts. A signing attempt produces a candidate signature, checks it against several bounds, and throws the whole attempt away if any bound is violated. Algorithm 7 of FIPS-204 has this shape, with irrelevant lines elided:
Note the structure: lines 25-28 sit inside the else branch. They are reached only by attempts that already survived line 23. This turns out to matter a great deal later.
There are four rejection conditions in total, and they fall into two quite different categories:
| Line | Condition | Character |
|---|---|---|
| 23 | \(\lVert z \rVert_\infty \ge \gamma_1 - \beta\) | security-mandatory |
| 23 | \(\lVert r_0 \rVert_\infty \ge \gamma_2 - \beta\) | security-mandatory |
| 28 | \(\#\{i : h_i = 1\} > \omega\) | encoding (compression) |
| 28 | \(\lVert c \cdot t_0 \rVert_\infty \ge \gamma_2\) | hint correctness (compression) |
The two on line 23 are required for the scheme to be secure. Without them the distribution of \(z\) would depend on the private key \(s_1\), and an attacker watching signatures could recover it. The rejection is exactly what makes the output distribution independent of the secret - it is the “Aborts” in Fiat-Shamir with Aborts.
The two on line 28 have nothing to do with security. ML-DSA publishes only the high part of \(t\), dropping \(d = 13\) low bits into \(t_0\), and the signer must transmit hints so the verifier can reconstruct what was dropped. If an attempt needs more hints than the signature format reserves room for, the signature is perfectly secure but cannot be encoded, so it gets discarded. The fourth condition similarly protects the correctness of the hint mechanism.
The Dilithium (v3.1) specification was careful about this. It describes the quantity as “the probability that Step 21 passes”, and labels the corresponding row of its Table 2 “Repetitions (from Eq. (5))”. It also mentions the second rejection point, but bounds it only loosely - “between 1 and 2%” - and gives no formula for it. FIPS-204 reproduced the numbers without the qualifier, stating that Table 1 contains the expected repetitions in the rejection sampling loop of ML-DSA.Sign_internal.
Fixing probability computation
Let’s assume \(p\) is a probability that a single attempt is accepted. Because the checks happen in two groups, with the second evaluated only if the first passed:
\[ \begin{aligned} p &= P(\text{line 23 passes}) \cdot P(\text{line 28 passes} \mid \text{line 23 passed}) \\ &= P_{norm} \cdot (1 - P_{ct_{0}}) \cdot (1 - P_{hint}) \end{aligned} \]
where \(P_{norm}\) is the probability of surviving both line-23 checks, \(P_{ct0}\) the probability that \(\lVert c \cdot t_0 \rVert_\infty\) reaches \(\gamma_2\), and \(P_{hint}\) the probability of producing more than \(\omega\) hints. The three terms turn out to need three completely different techniques - exact counting, a closed-form distribution, and simulation - which is most of what makes this interesting.
The Security Checks
Line 23 rejects unless every coefficient of \(z\) and every coefficient of \(r0\) is inside its bound. Both are handled by the same counting argument.
The z check
The condition is \(\lVert z \rVert_\infty \lt \gamma_1 - \beta\) , where \(z = y + c \cdot s1\). Take one coefficient \(z_i = y_i + (c \cdot s_1)_i\). The only randomness is \(y_i\), which \(ExpandMask\) algorithm draws uniformly from \(2 \cdot γ1\) possible values. The permitted range in which \(z_i\) may land in, is an open interval \((-(\gamma_1 - \beta), \gamma_1 - \beta)\), hence there are \(2(\gamma_1 - \beta) - 1 \quad\) admissible values.
This count does not depend on the value of \((c \cdot s_1)_i\). The per-coefficient probability is therefore the same whatever the secret key happens to be:
\[ P(\text{coefficient of } z \text{ passes}) = \frac{2(\gamma_1 - \beta) - 1}{2\gamma_1} \]
This factor is exact. It is a counting argument over a distribution that is uniform by construction, with no approximation and no assumption.
The \(r_0\) check
The condition is \(\lVert r_0 \rVert_\infty \lt \gamma_2 - \beta\), with \(r_0 = LowBits(w - c \cdot s_2)\) taking one of \(2 \cdot \gamma_2\) possible values. The identical count gives
\[ P(\text{coefficient of } r_0 \text{ passes}) = \frac{2(\gamma_2 - \beta) - 1}{2\gamma_2} \]
This factor is not exact. It assumes the low bits of \(w - c \cdot s2\) are uniformly distributed over their residues. They are not sampled - they are a deterministic function of \(A\), \(y\), \(c\) and \(s_2\) - so this is a heuristic, resting on the expectation that modular reduction of a pseudorandom quantity scrambles the low-order bits.
Putting them together
An attempt passes line 23 only if every coefficient passes. One violation anywhere kills the attempt. There are \(256 \cdot l\) coefficients in \(z\) and \(256 \cdot k\) in \(r_0\), treated as independent, so:
\[ P_{norm} = \left[\frac{2(\gamma_1-\beta)-1}{2\gamma_1}\right]^{256 \ell} \cdot \left[\frac{2(\gamma_2-\beta)-1}{2\gamma_2}\right]^{256 k} \]
Equation (5) of the Dilithium specification is an approximation of this product. Two things are worth separating. It is an approximation, good to about 1%, which the exact product above fixes. And it covers only the line-23 checks, whereas FIPS-204 presents it as the whole loop - which is the larger error, and needs the two remaining terms.
The Hint-Correctness Check
This is the smallest of the three terms and, as it turns out, the one with the cleanest answer. I am taking it before \(P_hint\) because the distribution it needs - that of a coefficient of \(c \cdot t_0\) - is needed by both.
What the check does
ML-DSA compresses its public key. The full value \(t = A \cdot s_1 + s_2\) is split by \(Power2Round\) into a high part \(t_1\), which is published, and a low part \(t_0\) of \(d = 13\) bits, which is not. The verifier therefore cannot compute the high bits of \(A \cdot z - c \cdot t\) directly, and the signer sends hints recording where the missing \(c \cdot t_0\) term causes a carry across a high-bit boundary.
The hint mechanism is only guaranteed to work when the perturbation is small. The governing lemma requires it to be at most \(\alpha \over 2\) with \(\alpha = 2 \cdot \gamma_2\). here the perturbation is \(-c \cdot t_0\), so the signer checks \(\lVert c \cdot t_0 \rVert_{\infty} < \gamma_2\) before trusting the hint. If the check fails the signature might not verify, so the attempt is discarded.
The distribution of a coefficient of \(c \cdot t_0\)
\(Power2Round\) defines \(t_0 = t \bmod^{\pm} 2^d\), where \(\bmod^{\pm}\) is the centred representative. So the coefficients of \(t_0\) lie in
\[ (-2^{d-1},\ 2^{d-1}] = (-4096,\ 4096] \quad \text{for } d = 13 \]
That is \(2^d = 8192\) consecutive integers, centred on zero. The centring is not incidental - it makes the distribution zero-mean, which is what lets \(c \cdot t_0\) be treated as a zero-mean sum. Assuming these coefficients are uniform over their 8192 values (the same class of heuristic as before), the variance of a uniform over \(N\) consecutive integers is \((N^2-1)/12\), so
\[ \mathrm{Var}(t_{0,i}) = \frac{2^{2d}}{12} = 5{,}592{,}405 \qquad \sigma(t_{0,i}) \approx 2365 \]
The challenge polynomial \(c\), produced by \(SampleInBall\), has exactly \(\tau\) non-zero coefficients, each \(+1\) or \(-1\), the rest zero. So each coefficient of the product \(c·t_0\) is a signed sum of exactly \(τ\) coefficients of \(t_0\).
Two consequences follow, and they point in different directions. Variances add for independent terms, so the spread is
\[ \sigma = 2^d \sqrt{\tau/12} \]
giving 14768, 16554 and 18318 for the three parameter sets. But the sum also has bounded support: each term contributes at most \(2^(d-1) = 4096\), so
\[ |(c \cdot t_0)_i| \le \tau \cdot 2^{d-1} \]
Irwin-Hall distribution
A sum of uniform variables is, by definition, Irwin-Hall distributed. Not approximately - exactly. And unusually for a continuous distribution, its CDF has a closed form:
\[ P(\mathrm{IH}_n \le x) = \frac{1}{n!}\sum_{j=0}^{\lfloor x \rfloor} (-1)^j \binom{n}{j} (x-j)^n \]
Two properties make it the right tool here:
- Its support is bounded - \(IH_n\) lies in \([0, n]\) and nowhere else - which is precisely what the normal approximation lacks.
- The sum above is finite and directly computable.
The signs of \(c\) can be ignored, since the uniform range is symmetric about zero and negating a symmetric variable leaves its distribution unchanged. Rescaling by the interval width \(2^d\) puts the threshold at \(x = \frac{\gamma_2}{2^d} + \frac{\tau}{2}\) in Irwin-Hall units.
| threshold x | IH support | P_ct0 | |
|---|---|---|---|
| ML-DSA Variant | |||
| ML-DSA-44 | 31.12 | [0, 39] | 7.33e-09 |
| ML-DSA-65 | 56.47 | [0, 49] | 0 |
| ML-DSA-87 | 61.97 | [0, 60] | 0 |
One calculation, no special cases. For ML-DSA-65 and ML-DSA-87 the threshold lands beyond the support of the distribution - 56.47 against a maximum of 49, and 61.97 against a maximum of 60 - and the tail beyond the support of a distribution is exactly zero. The condition cannot fire at all for those parameter sets.
The same result without any distribution
Those two zeros can be had more directly, and on weaker assumptions. Since \(|(c \cdot t_0)_i| \le \tau \cdot 2^{d-1}\) always:
| Variant | \(\tau \cdot 2^{d-1}\) | \(\gamma_2\) | Can the check fire? |
|---|---|---|---|
| ML-DSA-44 | 159,744 | 95,232 | yes |
| ML-DSA-65 | 200,704 | 261,888 | no |
| ML-DSA-87 | 245,760 | 261,888 | no |
For ML-DSA-65 and ML-DSA-87 the largest value \(c \cdot t_0\) can possibly attain is below the threshold, so the condition is unsatisfiable. This is the same fact as “x exceeds the Irwin-Hall support”, stated in unscaled units - not a different method. Its value is that it holds for any \(t_0\) in the valid range, and so does not depend on the uniformity assumption at all. The ML-DSA-44 figure, by contrast, does.
In theory, this check could be skipped for MLDSA-65 and -87, in practice not sure that would be FIPS-approved.
The Hint-Weight Rejection
This is the term FIPS-204 omits entirely, and the larger of the two missing corrections.
What needs to be computed
Line 26 of the algorithm, computes a vector of hints, one bit per coefficient, so \(h\) holds \(256 \cdot k\) bits. Line 28 rejects when the number of 1 bits exceeds \(\omega\) - the number of hint positions the signature format reserves space for. Writing \(N\) for that count:
\[ P_{hint} = P(N > \omega) \]
Notice what kind of object this is. \(P_norm\) and \(P_{ct_0}\) each concerned a single quantity crossing a threshold. Here the question is about a count of events across thousands of coefficients. That is a structurally harder problem, and it is why this term resisted a closed-form treatment.
Condition to fire single hint
\(\mathrm{MakeHint}(z, r)\) returns 1 when \(\mathrm{HighBits}(r)\) differs from \(\mathrm{HighBits}(r + z)\). Line 26 invokes it as
\[ h = \mathrm{MakeHint}(-c \cdot t_0,\ w - c \cdot s_2 + c \cdot t_0) \]
so \(r = w - c \cdot s_2 + c \cdot t_0\) and \(r + z = w - c \cdot s_2\). A hint at position \(i\) therefore fires exactly when adding \((c \cdot t_0)_i\) changes the high bits of \((w - c \cdot s_2)_i\) - that is, when its low part is pushed out of \((-\gamma_2,\ \gamma_2]\).
That low part is \(r_0\), the very quantity checked on line 23. And here the structure of the algorithm matters. Lines 25-28 live inside the else branch, reached only when line 23 already passed. So by the time hints are computed, \(r_0\) is not free to take any value in \((-\gamma_2,\ \gamma_2]\); it is already confined to \(|r_0| < \gamma_2 - \beta\), a narrower range.
Counting admissible values of \(r_0\) exactly, with \(a = |(c \cdot t_0)_i|\) and \(r_0\) uniform over the \(2(\gamma_2 - \beta) - 1\) values line 23 permits: for \(a > 0\) the hint fires when \(r_0\) exceeds \(\gamma_2 - a\), which happens for \(\max(0,\ a - \beta - 1)\) of them. The opposite side is unreachable. So
\[ P(\text{hint at } i \mid |(c \cdot t_0)_i| = a) = \frac{\max(0,\ a - \beta - 1)}{2(\gamma_2 - \beta) - 1} \]
Two consequences. No hint is possible at all unless \(|(c \cdot t_0)_i|\) exceeds \(\beta\). And the expression one would write without noticing the conditioning - \(a / (2\gamma_2)\) - overstates the hint rate by roughly 10 to 30 percent depending on parameter set.
Monte Carlo
Each trial simulates one signing attempt that has already passed line 23:
- sample \(c\): \(\tau\) positions among 256, each \(\pm 1\), rest zero
- sample \(t_0\): \(k\) polynomials of 256 coefficients, uniform on \((-2^{d-1},\ 2^{d-1}]\)
- compute \(c \cdot t_0\) in \(\mathbb{Z}[X]/(X^{256}+1)\)
- for each of the \(256 \cdot k\) coefficients, compute its hint probability and draw the Bernoulli outcome
- \(N\) = number of hints; record whether \(N > \omega\)
\(P_{hint}\) is the fraction of trials in which \(N\) exceeded \(\omega\). The product in step 3 is computed by negacyclic FFT: weight both operands by \(\exp(i \pi j / 256)\), do an ordinary cyclic convolution, unweight. Values stay below \(\tau \cdot 2^{d-1} = 245{,}760\), far under \(q/2\), so no modular reduction is needed and double precision is amply accurate. A direct sparse convolution is correct but about two orders of magnitude slower, which matters when you need hundreds of thousands of trials.
| mean hint count | omega | P_hint | |
|---|---|---|---|
| ML-DSA Variant | |||
| ML-DSA-44 | 63.0 | 80 | 0.01464 ± 0.00016 |
| ML-DSA-65 | 38.2 | 55 | 0.00374 ± 0.00008 |
| ML-DSA-87 | 56.7 | 75 | 0.00775 ± 0.00011 |
The mean hint counts sit comfortably below \(\omega\) in every case - the parameter sets were chosen that way - and it is only the upper tail of the count that spills over. Two sanity checks came out right: the simulated means match the analytic prediction, and the simulation recorded zero occurrences of the \(\lVert c \cdot t_0 \rVert_{\infty} \ge \gamma_2\) condition across 1.8 million attempts, consistent with the \(P_{ct_0}\) figures above.
Results
Putting the three terms together:
| P_norm | P_ct0 | P_hint | p | 1/p | measured | FIPS-204 | |
|---|---|---|---|---|---|---|---|
| ML-DSA Variant | |||||||
| ML-DSA-44 | 0.23272 | 7.3e-09 | 0.01464 | 0.22932 | 4.361 | 4.358 | 4.25 |
| ML-DSA-65 | 0.19539 | 0 | 0.00374 | 0.19466 | 5.137 | 5.137 | 5.1 |
| ML-DSA-87 | 0.25809 | 0 | 0.00775 | 0.25609 | 3.905 | 3.905 | 3.85 |
The derived values agree with independent measurement to 0.06%, 0.003% and 0.002%. That agreement is the real evidence that the modelling assumptions - the two uniformity heuristics and the independence assumptions in the Monte Carlo - are adequate at this precision. None of them is provable; all of them are testable, and they pass.
Everything downstream is now just the geometric distribution evaluated at these values of p.
| ML-DSA-44 | ML-DSA-65 | ML-DSA-87 | |
|---|---|---|---|
| Iterations | |||
| 1 | 22.93% | 19.47% | 25.61% |
| 2 | 40.60% | 35.14% | 44.66% |
| 3 | 54.23% | 47.77% | 58.83% |
| 4 | 64.72% | 57.94% | 69.37% |
| 5 | 72.81% | 66.12% | 77.22% |
| 6 | 79.05% | 72.72% | 83.05% |
| 7 | 83.85% | 78.03% | 87.39% |
| 8 | 87.55% | 82.31% | 90.62% |
| 9 | 90.41% | 85.75% | 93.02% |
| 10 | 92.61% | 88.52% | 94.81% |
| 11 | 94.30% | 90.76% | 96.14% |
| 12 | 95.61% | 92.56% | 97.13% |
| ML-DSA-44 | ML-DSA-65 | ML-DSA-87 | |
|---|---|---|---|
| Target | |||
| 90% | 9 | 11 | 8 |
| 95% | 12 | 14 | 11 |
| 99% | 18 | 22 | 16 |
Every variant reaches at least 90% within 11 iterations, but the tail runs long. ML-DSA-65 needs 22 iterations to reach 99%.
Check It Yourself
The agreement claimed above is the load-bearing evidence for the modelling assumptions, so it should not have to be taken on trust. The panel below runs mldsa-ref compiled to WebAssembly and measures the acceptance probability in your browser, against the derived value from the table above.
Loading WebAssembly…
The key count is the control worth experimenting with. \(P_{hint}\) depends on the key through \(t_0\), so the per-attempt acceptance probability is not identical for every key, and an average taken over too few keys estimates those keys’ value rather than the population’s. That kind of bias does not shrink as you add signatures - it shrinks as you add keys.
A caveat on what this panel can and cannot show. Ten thousand browser signatures give a standard error of roughly 0.04 on the mean - enough to confirm the derived value, not enough to argue with it. The 200,000 setting brings that to about 0.009, which is genuinely useful, at the cost of several minutes of your CPU.
Conclusion
The error in FIPS-204 Table 1 is small in magnitude and entirely benign for security, but it is instructive about how numbers travel between documents.
The Dilithium specification computed the probability it needed for its security argument, scoped the claim correctly, and said so twice - in the surrounding text and in the label of the table row. It also acknowledged the second rejection point, bounded it loosely at “between 1 and 2%”, and never computed it, because it did not need to. Every statement in that document is true.
FIPS-204 needed a different quantity - the cost of the loop, not the probability of one of its checks - and reused the available number. The qualifier did not survive the move. Nobody was careless, the figure was simply asked to answer a question it was never computed for.