What the ML-DSA Proof Actually Rests On: MLWE, SelfTargetMSIS and the Quantum Random Oracle

Most engineers will meet ML-DSA as one line in a design document: post-quantum, standardized, strongly unforgeable. That line is true, but it is a compressed summary of a mathematical argument with specific premises, specific losses and a specific history, including a gap that was found and closed after the scheme had already been selected. If you are going to let a key sign agent tool calls, release model weights or anchor an audit trail for a decade, you should know which of those premises you are betting on. This article opens the argument clause by clause, without formulas, and ends with an assurance statement you can defend line by line.

The sentence in the standard, and the question it hides

Section 3.1 of FIPS 204 says that ML-DSA is designed to be strongly existentially unforgeable under chosen-message attack, abbreviated SUF-CMA. In that game an adversary may ask the honest signer to sign any messages it likes, adaptively, and it wins if it outputs any valid message and signature pair that the signer did not produce, including a fresh signature on a message the signer has already signed. Section 3.2 then says that the security of ML-DSA is based on the Module Learning With Errors problem, MLWE, and on a non-standard variant of the Module Short Integer Solution problem called SelfTargetMSIS, attributing the name to Kiltz, Lyubashevsky and Schaffner (2018). Two words in those sentences deserve attention: designed, and based. Neither one says proved from standard assumptions alone, and the distance between those phrasings is the subject of this piece.

To read the argument we need four terms. A reduction is an algorithm that turns any successful attacker on the signature into a solver for some hard problem; if the problem is hard, the attacker cannot exist. A reduction is tight when the solver it builds is about as fast and as successful as the attacker, and loose when it loses a large factor, for example one proportional to the number of hash queries the attacker makes. The random oracle model, or ROM, is the idealization in which the hash function is replaced by a truly random function that the adversary can only evaluate by asking for it. The quantum random oracle model, or QROM, gives the adversary the extra power to query that ideal function on a superposition of inputs, which is what a quantum computer running the real hash function could do.

For orientation, ML-DSA is a Fiat-Shamir signature with aborts, a paradigm introduced by Lyubashevsky (2009): the signer commits to a masked value, derives a challenge by hashing that commitment with a message representative, responds with the mask plus the challenge times the secret, and discards any response whose distribution would reveal the secret. Nothing in this article depends on the details of that loop beyond two facts: the challenge comes from a hash, and signing may repeat several times before it outputs anything. Everything else here concerns what can be concluded about such a scheme, under which assumptions, and with what loss.

Three problems, three different jobs

The CRYSTALS-Dilithium specification, version 3.1, states the concrete result that FIPS 204 inherits. If the hash is modelled as a quantum random oracle, an adversary's advantage in breaking strong unforgeability is at most the sum of four terms: the advantage of some algorithm against MLWE, the advantage of some algorithm against SelfTargetMSIS, the advantage of some algorithm against MSIS, and a fixed term of two to the minus 254. The specification adds that the ratio of running time to success probability for the attacker is within a small multiplicative factor of the best such ratio among the three derived solvers. In plain terms, the bound is tight, and it decomposes the security of the signature into three separate bets.

Each bet guards a different door. MLWE is a decision problem: given a random public matrix and a vector, decide whether the vector is uniformly random or is the matrix times a short secret plus a short error. The ML-DSA public key is exactly such a vector, so MLWE is what stops key recovery and, inside the proof, what lets the analysis swap a real public key for a random-looking one. MSIS asks for a nonzero vector with small coefficients that the public matrix sends to zero. SelfTargetMSIS fuses the lattice with the hash: given a random matrix and target, the solver must find a short vector and a message digest such that hashing the digest together with the lattice image of that vector reproduces the challenge embedded in the vector itself. The target is self-referential because the solver chooses where to aim and the hash decides whether it hit.

The specification is explicit about the division of labour: MLWE protects against key recovery, SelfTargetMSIS is the assumption on which forgery of a new message rests, and MSIS is needed only for strong unforgeability. That last point is worth a pause. Plain unforgeability, which forbids signatures on new messages, needs only the first two. The extra clause that forbids a second, different valid signature on an already signed message is paid for by MSIS: two distinct short responses that verify against the same commitment and challenge differ by a short vector that the matrix maps to something tiny, which is an MSIS solution. A system that relies on signatures being unique per message is therefore relying on one more lattice assumption than a system that only needs authenticity.

The fourth term in the bound is small, but the conditions attached to it are not. A footnote in the specification states that the simplified bound assumes the matrix expansion produces a uniform matrix, the mask expansion is a perfect pseudorandom function, and the hash is perfectly collision resistant. Those are modelling choices about SHAKE, not lattice assumptions, and they sit underneath everything else. When an analysis says ML-DSA is secure under MLWE and SelfTargetMSIS, it silently includes them.

Why the classical proof stops at the quantum boundary

Against a classical adversary there is a well-known route from SelfTargetMSIS to plain MSIS, the forking lemma of Pointcheval and Stern, sketched in the Dilithium specification. Run the forger until it outputs a forgery whose challenge came from one particular hash query. Rewind the forger to just before that query, answer it with a fresh random challenge, and let it run forward. With probability roughly one over the number of hash queries it forges at the same point with the new challenge. Two short responses for the same commitment under two different challenges subtract to a short vector in the kernel of the matrix, which is an MSIS solution. The reduction is loose, because of that one-over-the-number-of-queries factor and the rewinding, but it means that in the classical world SelfTargetMSIS is no harder to trust than MSIS.

The quantum adversary breaks this route at its first step. The forking lemma needs to identify which hash query mattered and to restart the adversary from the moment of that query. When the adversary queries the hash on a superposition, the reduction cannot copy or inspect the adversary's state without disturbing it, and recording the query in the classical sense collapses the very superposition that gives the adversary its power. The Dilithium specification says plainly that the forking lemma, being a form of rewinding, does not give a quantum reduction from MSIS to SelfTargetMSIS. Work by Ambainis, Rosmanis and Unruh (2014), cited there, showed that no black-box proof of the Fiat-Shamir transform's security in the QROM can exist in general. So in the quantum setting, which is the only setting that motivates a post-quantum signature, SelfTargetMSIS is not derived from anything. It is assumed.

The designers give three reasons to accept that assumption, all stated in the specification and all worth weighing on their merits. First, no natural signature built from a three-move protocol through Fiat-Shamir is known that is secure in the ROM but broken in the QROM. Second, SelfTargetMSIS is a convolution of a lattice problem with a hash function that has no algebraic relationship to the lattice, so a shortcut would have to exploit a correlation that nobody has found. Third, later results narrowed the distance: Don, Fehr, Majenz and Schaffner (2019) showed that Fiat-Shamir is QROM-secure when the underlying protocol is collapsing and specially sound, and Liu and Zhandry (2019) gave a non-tight reduction from MLWE to the collapsing property. None of these is a proof of SelfTargetMSIS from standard lattice problems with tight parameters. Together they are strong circumstantial evidence, and it is honest to call them that.

Insurance with a known premium: the lossy variant

Kiltz, Lyubashevsky and Schaffner did more than name SelfTargetMSIS. Their framework has two steps. The first shows, tightly and in the QROM, that for deterministic signatures whose identification protocol is zero-knowledge, security against chosen-message attack follows from security against an adversary who sees only the public key and never queries a signing oracle, a notion called UF-NMA. The second shows that if the identification protocol has lossy keys, meaning public keys that look normal but for which a valid response almost never exists, then UF-NMA reduces tightly to the problem of telling real keys from lossy ones. For a lattice scheme that distinguishing problem is MLWE.

They instantiated this by choosing Dilithium parameters under which SelfTargetMSIS becomes information-theoretically hard, so that the forgery term disappears and only MLWE remains. The cost is the interesting part. According to the paper's abstract, the original Dilithium of that time had public keys of about 1.5 kilobytes and signatures of about 2.7 kilobytes, while the variant based tightly on MLWE alone had public keys of about 7.7 kilobytes and signatures of about 5.7 kilobytes at the same security level. The 3.1 specification summarizes the trade as roughly two times larger signatures and five times larger public keys, and states that the designers did not consider it a good trade, while noting that its existence adds confidence in the optimized scheme.

Here is the synthesis this article proposes. The lossy variant turns a qualitative doubt into a priced option. If SelfTargetMSIS were ever weakened in a way that left MLWE intact, the community would not be starting from nothing; there is a known construction whose security rests on MLWE alone, with a known size penalty. That is a stronger position than most deployed cryptography enjoys, and it is a concrete reason to treat the non-standard assumption as a moderate rather than an alarming risk. It also identifies the right early-warning signal: research that relates SHAKE's structure to module lattices, or that improves quantum algorithms for problems combining hashing with short vectors, matters more to ML-DSA than generic progress on hash functions alone.

Tightness, signing randomness and a decision NIST reversed

The first step of the Kiltz-Lyubashevsky-Schaffner framework is stated for deterministic signatures, where the mask is derived from the key and message so that each message has exactly one signature. A footnote in the Dilithium 3.1 specification records what happens otherwise: the deterministic requirement can be relaxed, and the proof simply loses a factor equal to the number of different signatures produced per message. The authors illustrate this with a signer deployed on several devices with different random-number generators and conclude that security would not be affected much. That is a reasonable reading for small numbers. It is still a loss, and it explains a design choice that otherwise looks odd.

Version 3.1 of Dilithium suggested deterministic signing as the default, except where an adversary could mount side-channel attacks that exploit determinism. FIPS 204 reversed that default. Section 3.4 specifies a hedged procedure in which a 32-byte value called rnd, drawn from a random bit generator, is mixed with the private seed and the message representative to derive the mask, and permits a deterministic variant, with rnd fixed to zeros, only where fresh randomness is unavailable. Appendix D.2 records the change. In proof terms, NIST accepted a reduction that is looser by the number of distinct signatures per message, in exchange for resistance to the fault and side-channel attacks that deterministic lattice signing invites. How those attacks work, and which of them the rnd input actually stops, is a separate question with its own evidence; here the point is only that the default was a deliberate trade between a proof parameter and an engineering risk.

There is one more quantity in the contract that rarely appears in summaries. The security considerations of RFC 9881, which profiles ML-DSA for X.509, state that for estimating security strength it has been assumed that the attacker has access to signatures for no more than two to the 64th chosen messages. That bound is astronomically large for a person and merely very large for a machine. An agent identity that signs every tool call, every inter-agent message and every log batch could, over years and across replicas sharing a key, sign far more than any human signer. It will not approach two to the 64th in practice, but the existence of the parameter is a reminder that the proof counts signing queries, and that key-per-workload rotation is cheap insurance for both this bound and the tightness factor above.

The 2023 gap, and what its repair teaches

In 2023 two groups published careful re-examinations of the proofs behind Fiat-Shamir with aborts. Don, Fehr and Huang (IACR ePrint 2023/246) report that while formalizing a variant of the Kiltz-Lyubashevsky-Schaffner QROM proof they uncovered a subtle but crucial gap in the step that reduces chosen-message security to no-message security. That step must simulate the signing oracle without the secret key, using the zero-knowledge property of the identification protocol, and the aborts make that simulation more delicate than in ordinary Schnorr-type schemes. The gap, they write, was confirmed by the original authors and had no simple patch. They supplied new proofs of that step in both the ROM and the QROM, performed a concrete analysis showing that Dilithium's claimed security level remains valid, and produced a fully machine-checked ROM proof of Dilithium's chosen-message security in the EasyCrypt proof assistant.

Devevey, Fallahpour, Passelegue, Stehle and Xagawa (IACR ePrint 2023/245) widened the lens. They point out that most analyses assume a bounded number of aborts, where signing gives up after a fixed number of attempts, while practical schemes such as Dilithium loop until a signature appears, and that combining random oracles with such loops creates technicalities for correctness, run time and security in both cases. They identify errors in all the analyses that existed at the time, give two corrected QROM analyses for the bounded case, prove that the underlying protocol meets a stronger zero-knowledge notion than is usually considered for protocols with aborts, and treat the unbounded case separately.

FIPS 204 reflects the bounded-versus-unbounded question directly. Appendix C says implementations should not cap the signing loop, but if they do, the cap must be at least 814 iterations, a limit chosen so that a correct implementation reaches it with probability of about two to the minus 256, against expected repetition counts of 4.25, 5.1 and 3.85 for the three parameter sets. Read with the 2023 papers, that table is not an implementation detail. It is where the proof's model of the loop meets the code's model of the loop.

The lesson is about the type of evidence, not about alarm. The scheme did not change; the argument for it did. A standard's security rests on three supports that fail independently: years of cryptanalysis that found no practical attack, a proof that relates attacks to named problems, and checking of that proof by people and, increasingly, by machines. The 2023 episode shows the second support can crack while the first stands, and that the third is how such cracks are found. A mature assurance claim cites all three.

What the proof does not cover

A reduction is only as wide as its model, and several things a deployment depends on lie outside ML-DSA's. The concrete hardness of MLWE and MSIS at the chosen parameters is not established by the proof at all; it comes from cryptanalytic cost estimates for the best known lattice attacks, which is why the parameter sets are assigned to NIST security categories two, three and five rather than proven to meet them. The proof treats SHAKE as ideal. And the proof assumes the signer computes exactly the algorithm on exactly the specified inputs.

That last assumption is where engineering re-enters. FIPS 204 Section 3.6.1 sets requirements on the generator that produces the key-generation seed: at least 192 bits of security strength for ML-DSA-65 and 256 for ML-DSA-87, and for ML-DSA-44 at least 128, with the claimed category dropping from two to one if a generator below 192 bits is used. Section 3.6.2 requires verifiers to reject keys and signatures of the wrong length and warns that failing to do so may interfere with strong unforgeability. A key generated from a weak seed, or a verifier that tolerates malformed encodings, falls outside the theorem even though the mathematics is untouched. Faults and side channels are outside it too: the proof is about an ideal signer, and a signer that can be made to compute the wrong thing is a different object.

There is also a family of properties that strong unforgeability does not imply, such as whether a signature binds the specific public key or the specific message, studied by Cremers and co-authors (2021) under the name beyond unforgeability. FIPS 204 notes that ML-DSA hashes the public key into its message representative to obtain those properties. They rest mainly on collision resistance of the hash, not on the lattice bound discussed here, and they deserve their own analysis rather than an appendix to this one.

An honest assurance statement for agent and provenance keys

AI agents turn signatures into infrastructure. An agent identity may sign every tool invocation so that a gateway can attribute it; a pipeline may sign every model artifact so that a deployment can check provenance years later; a fleet may sign its own audit records so that an incident team can trust them. These keys are long-lived, they sign at machine rate, and the evidence they produce will be read by people who were not in the room when the algorithm was chosen. That is exactly the situation in which a vague assurance claim does damage, because nobody can tell later which assumption the system was betting on.

The statement this article recommends names every clause. It identifies the parameter set and the standard. It says that strong unforgeability is argued in the quantum random oracle model under MLWE, SelfTargetMSIS and MSIS, with SHAKE idealized, and that SelfTargetMSIS has no reduction from a standard lattice problem against quantum adversaries. It records the signing mode, hedged by default, and the per-key signing budget the deployment assumes, well inside the two to the 64th used in the IETF profile. It records the validation status of the implementation and the generator used for key generation. And for evidence meant to outlive the key by decades, such as release signatures on model weights, it records whether a second signature from a different assumption family, for example a hash-based scheme, is attached as a hedge.

None of this lowers confidence in ML-DSA. The scheme has a tight quantum argument, a priced fallback that removes its one non-standard assumption, a proof that has been checked hard enough to find and fix a real gap, and years of cryptanalysis behind its parameters. The point is to make that confidence inspectable. When an agent platform later asks whether its signing keys are still sound after some new result, an assurance statement written this way turns the question into a lookup: which clause did the result touch?

Practitioner Toolkit

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

KEY ASSURANCE STATEMENT
Key purpose: [agent identity | tool-call signing | model release | audit anchor]
Algorithm: ML-DSA-[44|65|87], NIST FIPS 204 (pure mode)
Security argument: SUF-CMA in the quantum random oracle model under MLWE (key recovery), SelfTargetMSIS (new-message forgery) and MSIS (second signatures); SHAKE idealized. SelfTargetMSIS has no known reduction from a standard lattice problem against quantum adversaries.
Proof status reviewed: KLS18 framework with the 2023 repair of the chosen-message step (Don-Fehr-Huang; Devevey et al.).
Signing mode: [hedged (default) | deterministic, justified by: ...]
Signing budget per key: [estimated signatures over lifetime] (the IETF profile assumes at most two to the power 64)
Key-generation generator strength: [bits]; meets FIPS 204 section 3.6.1 for this parameter set: [yes/no]
Implementation validation: [module, certificate or test evidence]
Assumption-diverse co-signature for evidence beyond [N] years: [none | hash-based scheme ...]
Re-review trigger: any result on SelfTargetMSIS, MLWE/MSIS estimates, or SHAKE structure.

Glossary

SUF-CMA

Strong existential unforgeability under chosen-message attack: no efficient adversary with a signing oracle can output any valid message-signature pair the signer did not produce.

Reduction

An algorithm that converts any successful attacker on a scheme into a solver for a named problem, so hardness of the problem implies security of the scheme.

Tight reduction

A reduction whose solver is about as fast and as successful as the attacker it is built from, so the scheme's security level matches the problem's.

Quantum random oracle model (QROM)

A proof model in which the hash is an ideal random function that the adversary may query on superpositions of inputs.

MLWE

Module Learning With Errors: distinguish a public matrix times a short secret plus short error from a uniformly random vector over a module of polynomials.

MSIS

Module Short Integer Solution: find a nonzero vector with small coefficients that a given random module matrix maps to zero.

SelfTargetMSIS

A non-standard problem combining a module lattice with a hash: find a short vector and digest whose hashed lattice image reproduces the challenge contained in that vector.

Forking lemma

A rewinding technique that reruns a forger with a reprogrammed hash answer to extract two related forgeries, valid for classical but not quantum adversaries.

Lossy identification

An identification scheme whose real public keys can be swapped for indistinguishable lossy keys under which valid responses almost never exist.

UF-NMA

Unforgeability under no-message attack: the adversary sees only the public key and never queries a signing oracle.

References

1. NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (2024)
2. Kiltz, Lyubashevsky and Schaffner, A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model (EUROCRYPT 2018), IACR ePrint 2017/916
3. Ducas et al., CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation, Version 3.1 (2021)
4. Don, Fehr and Huang, Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium, IACR ePrint 2023/246
5. Devevey, Fallahpour, Passelegue, Stehle and Xagawa, A Detailed Analysis of Fiat-Shamir with Aborts, IACR ePrint 2023/245
6. Lyubashevsky, Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (ASIACRYPT 2009)
7. Cremers, Duzlu, Fiedler, Fischlin and Janson, BUFFing Signature Schemes Beyond Unforgeability and the Case of Post-Quantum Signatures (IEEE S&P 2021), IACR ePrint 2020/1525
8. RFC 9881, Algorithm Identifiers for ML-DSA in the Internet X.509 PKI (2025), Security Considerations