ML-DSA: Fiat-Shamir with Aborts and the Transcript That Leaks Nothing

ML-DSA is best understood not as a bespoke signature but as an identification protocol frozen into one. In an identification protocol a prover convinces a verifier that it knows a secret, through a three-move exchange; the Fiat-Shamir transform collapses that interaction into a single non-interactive signature by having the prover generate the verifier's challenge itself, as a hash. Over module lattices this construction is efficient and compact, but it carries one deep hazard: the prover's response is computed from the secret key, and a careless response leaks it. The mechanism that closes this hole — rejection sampling, the aborts of the title — is the conceptual heart of the scheme, and this article builds up to it deliberately.

The identification protocol

The starting point is a three-move protocol over module lattices. The signer's secret is a pair of short vectors of ring elements; the public key packages them into a module-LWE instance, a matrix times the first short vector plus the second, so that recovering the secret from the public key is the module learning-with-errors problem. The three moves are a commitment, a challenge, and a response, and the whole signature is a transcript of one run of this exchange bound to the message.

The signer commits by sampling a fresh short masking vector and publishing a compressed form of the matrix applied to it — the commitment. The verifier replies with a challenge, a small polynomial with only a handful of plus-or-minus-one coefficients, cheap to multiply by. The signer responds with the masking vector plus the challenge times the secret. The verifier accepts if reapplying the matrix to the response, after subtracting the challenge times the public key, reproduces the commitment, and if the response is short. The algebra is arranged so that an honest signer's response always satisfies both checks.

This exchange is a proof of knowledge: passing it convinces the verifier that the responder knows a short secret consistent with the public key, because producing a valid short response for a random challenge without the secret would itself amount to solving a hard lattice problem. The signature will inherit its unforgeability from that fact — but only once two gaps are closed: making the protocol non-interactive, and preventing the response from leaking the very secret it proves knowledge of.

Fiat-Shamir: removing the verifier

A signature cannot involve an interactive verifier, so the Fiat-Shamir transform removes it. Instead of waiting for a challenge, the signer computes the challenge itself by hashing the commitment together with the message. Because the hash is modeled as a random function, the self-generated challenge is as unpredictable as a real verifier's would have been, and crucially it is bound to both the commitment and the message: any change to either produces a different challenge, so a transcript valid for one message cannot be replayed for another.

The resulting signature is the challenge and the response; the verifier recomputes the commitment from them via the lattice relation, rehashes it with the message, and checks that the hash matches the challenge in the signature and that the response is short. This is a complete non-interactive signature, and its security in the random oracle model follows from the identification protocol's soundness — with the essential caveat, for post-quantum use, that the argument must survive in the quantum random oracle model where the adversary can query the hash in superposition, which the standardized construction is designed to do.

One property of the transform is worth flagging because the next section depends on it. Fiat-Shamir requires the identification protocol to be honest-verifier zero-knowledge: a transcript produced with a random challenge must be simulable without the secret, revealing nothing about it. If the response leaked the secret, the transform would faithfully preserve that leak in every signature. Ensuring the transcript leaks nothing is therefore not optional polish; it is a precondition for the whole construction to be secure.

Why aborts are necessary

Here is the hazard in plain terms. The response is the masking vector plus the challenge times the secret. If the signer simply published it, the distribution of responses across many signatures would be centered on and skewed by the secret — each response is a noisy nudge in the secret's direction, and enough of them would triangulate it. A signature scheme that leaks its own signing key over repeated use is worthless, and this is exactly what a naive Fiat-Shamir lattice signature would do.

Rejection sampling fixes this. The signer fixes in advance a safe region — a bound within which a response could have arisen from many different secrets equally — and after computing a candidate response checks whether it lies inside that region. If it does, the signer publishes it; if it does not, the signer aborts this attempt, throws away the masking vector, and restarts with a fresh one. Because only responses inside the fixed region are ever published, the distribution of published responses is uniform over that region and provably independent of the secret. The transcript leaks nothing, satisfying the zero-knowledge precondition exactly.

The cost is that signing sometimes retries. The parameters are tuned so that the acceptance probability is a manageable fraction and a signature typically succeeds within a few attempts, trading a modest, variable number of restarts for the guarantee that the secret stays hidden. This rejection step is the with-aborts in Fiat-Shamir with aborts, and it is the single idea that makes lattice Fiat-Shamir signatures safe to use repeatedly.

The two hard problems

ML-DSA's security rests on two lattice assumptions playing distinct roles. The public key is a module-LWE instance, so recovering the secret from the public key alone is the module learning-with-errors problem — this is what protects the key from a passive attacker who merely reads the public key. Key secrecy is thus inherited directly from the same family of assumptions that underpins the key-encapsulation standard.

Unforgeability rests on a second problem, module short-integer-solution. A forger who does not know the secret must, to pass verification, produce a short response and a valid challenge satisfying the lattice relation for a message it chose — and doing that without the secret amounts to finding a short solution to a homogeneous module-lattice equation, the module-SIS problem. The security proof reduces a successful adaptive forger to an algorithm breaking one of these two problems, so a forgery implies solving module-LWE or module-SIS, both believed hard against classical and quantum attackers.

This two-problem structure is a feature. Key secrecy and unforgeability are protected by related but distinct assumptions, and both are the module-lattice problems examined earlier in this track, inheriting their worst-case-to-average-case foundations and their conservative parameter methodology. The signature is not resting on a novel or exotic hardness claim; it is the identification protocol's soundness and zero-knowledge translated into the two standard module-lattice problems.

Parameters, determinism, and deployment

ML-DSA is standardized in three parameter sets targeting the three security categories, with signatures on the order of a few kilobytes and public keys somewhat smaller — larger than pre-quantum elliptic-curve signatures but modest enough for general use, and much smaller than the hash-only alternative of the next article. Verification is fast, and signing is fast on average despite the occasional rejection-driven retry. For the great majority of applications ML-DSA is the efficient default among post-quantum signatures.

The standard also addresses how the masking randomness is generated. Pure deterministic signing, deriving the mask from the secret key and message, avoids dependence on a runtime random-number generator but can expose the scheme to fault attacks that perturb a computation; pure randomized signing depends on good entropy at signing time. FIPS 204 specifies a hedged approach that mixes a fresh random value with deterministic derivation, so that the scheme degrades gracefully if either the random source or the fault-freedom assumption fails. Implementers should follow the hedged construction rather than reverting to a purely deterministic or purely randomized variant.

For autonomous AI systems ML-DSA is the natural workhorse for signing at volume — authenticating model artifacts, signing agent-to-agent messages, issuing short-lived capability tokens — precisely because its signatures are small and its verification is cheap. The one discipline to enforce is that the rejection-sampling and hedged-randomness details are properties of a validated implementation, not knobs to reinvent: an agent framework should call a conformant ML-DSA library and must never attempt to skip the abort loop or simplify the mask generation to save cycles, since either shortcut can silently reintroduce the secret-leaking behavior the aborts exist to prevent.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

ml_dsa:
  implementation: conformant_validated_only
  abort_loop: never_skipped        # rejection sampling required
  mask_randomness: hedged           # per FIPS 204
  parameter_set: matched_to_category
hardness:
  key_secrecy: module_lwe
  unforgeability: module_sis
agent_use:
  reinvent_internals: forbidden

Glossary

Identification protocol

A three-move commit-challenge-response exchange by which a prover convinces a verifier it knows a secret.

Fiat-Shamir transform

A method that makes an identification protocol non-interactive by computing the challenge as a hash of the commitment and message.

Rejection sampling (abort)

Discarding and retrying any response that falls outside a fixed safe region, so the published response distribution is independent of the secret.

Honest-verifier zero-knowledge

The property that a protocol transcript with a random challenge can be simulated without the secret, revealing nothing about it — a Fiat-Shamir precondition.

Module-SIS

The module short-integer-solution problem: find a short nonzero solution to a homogeneous module-lattice equation; ML-DSA's unforgeability reduces to it.

Hedged randomness

FIPS 204's signing approach mixing fresh randomness with deterministic derivation, robust to failures of either the entropy source or fault-freedom.

References

1. NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (2024)
2. Ducas et al., CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme (IACR TCHES, 2018)
3. NIST FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (2024)
4. Lyubashevsky, Peikert & Regev, On Ideal Lattices and Learning with Errors over Rings (EUROCRYPT, 2010)
5. Langlois & Stehle, Worst-Case to Average-Case Reductions for Module Lattices (Designs, Codes and Cryptography, 2015)