The Fiat-Shamir with Aborts Loop in ML-DSA

A Schnorr signature is a proof of knowledge made non-interactive by hashing the commitment and the message together. The prover sends a commitment, the verifier sends a challenge, the prover responds with a value derived from the secret key and the challenge, and the verifier checks that the response reproduces the commitment. The construction is sound because anyone able to answer two different challenges for the same commitment can extract the secret key. That property is also the trap for lattice analogues: a response is a lattice vector, and holding two responses for one commitment exposes the relation between them.

ML-DSA, standardised as FIPS 204 from the CRYSTALS-Dilithium submission, solves this with rejection. The signer generates a candidate response and discards it unless it falls in a region where its distribution is independent of the secret. The rejection is the security mechanism, not an optimisation, and the fraction of candidates rejected is a fixed cost per signature.

The signature equation and what must be kept secret

The keys are a matrix $A$ of $k \times \ell$ polynomials over $R_q = \mathbb{Z}_q[X]/(X^{256}+1)$, a secret vector $s_1$ of $\ell$ short polynomials, and a secret vector $s_2$ of $k$ short polynomials. The public key is $t = A s_1 + s_2$. Verification resembles the ML-KEM public key equation in the ML-KEM noise walkthrough, and the same $q = 8380417$ used by Dilithium appears nowhere in the KEM; the signature scheme needs a larger modulus because the challenge-dependent response values are larger than KEM noise.

To sign a message $M$, the signer samples a masking vector $y$ with coefficients from a bounded distribution and computes a commitment

$$w = A y.$$

The challenge is $c = H(\mu | w)$ for a precomputed message digest $\mu$, where the hash output is interpreted as a polynomial with exactly $\tau$ coefficients equal to $\pm 1$ and the rest zero. The response is

$$z = y + c s_1,$$

and the signature is the pair $(c, z)$ with a hint allowing recovery of the high bits of $w$. Verification recomputes $w’ = A z - c t$, derives $c’ = H(\mu | w’)$, and accepts if $c’ = c$ and $z$ is short enough. Substituting the definitions gives

$$A z - c t = A(y + c s_1) - c(A s_1 + s_2) = A y - c s_2,$$

so the verifier recovers the commitment up to the term $c s_2$, which the hint absorbs.

Now consider what two signatures on the same commitment would reveal. If an attacker obtained $(c_1, z_1)$ and $(c_2, z_2)$ with $c_1 \neq c_2$ for the same $y$, then $z_1 - z_2 = (c_1 - c_2) s_1$, and $s_1$ is recoverable by division in the ring, provided the difference $c_1 - c_2$ is invertible. This is the same extraction argument as Schnorr, and it is not a weakness in the interactive protocol: it is proof that two valid transcripts for one commitment cannot both exist. The problem is that a non-interactive signature reveals the challenge, and if $z = y + c s_1$ is published with no restriction on $y$, then $z$ is a sample from a distribution centred at $c s_1$, and the mean of many samples estimates the secret. Signing twice with the same $y$ would be the direct analogue of ECDSA nonce reuse.

Bounding the response instead of the commitment

Lyubashevsky’s Fiat-Shamir with Aborts replaces the hiding of $y$ with a distributional argument. If $y$ is drawn from a distribution whose width is much larger than $c s_1$, then the sum $y + c s_1$ is statistically close to $y$ itself, and the published $z$ leaks nothing about $c s_1$. The “much larger” is quantified by the Rényi divergence between the two distributions, and the divergence is required to be bounded by a constant for the security proof to go through.

The straightforward way to use that fact is to sample $y$ from a wide distribution, compute $z$, and reject if any coefficient of $z$ exceeds a bound $\gamma_1$. The rejection is what makes the output distribution correct: conditioning $y + c s_1$ on lying inside a $\gamma_1$-ball gives a distribution that is, by the rejection-sampling lemma, exactly proportional to the conditional distribution of $y$ on the same ball. The signer loops until a candidate passes. Since $c s_1$ is small compared to $\gamma_1$, the acceptance probability is high, and the loop terminates quickly.

Dilithium’s actual construction adds a second bound. It rejects candidates where the high bits of $w$ change under the addition of $c s_2$, which the hint cannot cover; it also rejects candidates where $z$ violates the norm bound. The final scheme in FIPS 204 fixes $\gamma_1 = (q-1)/88$ and $\gamma_2 = (q-1)/32$ and specifies a bound on $|z|_\infty$ of $\gamma_1 - \beta$ where $\beta = \tau \eta$ is the maximum norm of $c s_1$. The acceptance rate is not published as a single number because it depends on the parameter set; the FIPS 204 text requires implementations to loop until acceptance and to derive fresh masking randomness on each iteration, with a specified mechanism for deriving the counter values.

There is a critical operational consequence: rejection means signing is not a fixed-time operation. The number of iterations is a random variable with a geometric-like distribution, and if the signer’s randomness is deterministic per message, the retry counter must be part of the derivation. A deterministically seeded signer that restarts the counter at zero on each call would produce the same $y$ for the same message, and while re-verifying the same signature is harmless, the security argument for reuse of masking randomness within one signing operation relies on the counter advancing.

Verifying without recovering the full commitment

Verification needs to compute $A z - c t$ and must decide whether the challenge hash matches. The hint mechanism is what makes this possible: the signature includes a vector of bits flagging which coefficients of $w$ had a carry when the low bits were discarded. Without it, the verifier would have to recover the full $w$ exactly, which means reproducing the low bits of $A y$, which is impossible without $y$.

The high-bit decomposition splits each coefficient $w_i$ into $w_i = w_{i,1} \cdot 2\gamma_2 + w_{i,0}$ where $w_{i,1}$ is the high part in $[0, 15]$ and $w_{i,0}$ is the low part in $[-\gamma_2, \gamma_2]$. The hint records whether $w_{i,0}$ exceeded $\gamma_2$ during the computation, which would have caused the high part to wrap. Verification recomputes $A z - c t$, takes the high bits, applies the hint, and hashes.

Two failure modes dominate. The first is hint decoding: the hint vector is serialised as a sparse structure with a per-row count byte followed by the indices, and the number of nonzero hints per row is bounded in the standard. A malformed hint can cause out-of-bounds reads if the implementation trusts the count, so the parser must validate the count against the bound before indexing. The second is norm checking: verifying that $z$ is within the bound requires computing the maximum absolute coefficient, which for a 256-coefficient polynomial is a 256-element reduction. Implementations that compare with a vectorised absolute-value-and-maximum over signed 32-bit words must handle the case where a coefficient equals the minimum representable value, though the standard’s encoding range avoids the extreme.

Signature and key sizes against the older standard

The sizes reflect the parameters rather than the machinery. ML-DSA-44 has a 1312-byte public key and a 2420-byte signature; ML-DSA-65 has 1952 and 3309 bytes; ML-DSA-87 has 2592 and 4627 bytes. The verification cost is dominated by the matrix-vector multiplication $A z$, which is $\approx k \ell$ polynomial multiplications: for ML-DSA-65 that is $6 \times 5 = 30$ multiplications, each over 256 coefficients with a 23-bit modulus. The signing cost is dominated by the same product plus the rejection loop, so signing is several times more expensive than verification.

Against this, the same parameter set offers the additional structure that RSA-2048 signatures of 256 bytes cannot. A 3309-byte signature is around thirteen times the RSA equivalent and would be unwieldy in a certificate chain if every leaf carried one. This is the reason the ecosystem migration is not uniform: firmware and protocol headers with hard size limits adopt different trade-offs from server certificates. The composition choices are visible in hybrid certificate and signature migration, where the signature size budget is often the binding constraint.