Rejection Sampling
Rejection sampling is the reason ML-DSA sometimes throws away a signature it just computed and starts over. In a lattice signature the natural, first-try response is a combination of the signer’s secret key and some fresh randomness, and the trouble is that this combination is skewed by the secret. Publish enough of these skewed responses and a patient attacker can average out the randomness and read the secret key straight off the pile. Rejection sampling closes that leak. After computing a candidate signature the signer checks whether it lands in a safe region, and if it does not, the signer discards it and retries with new randomness. Only responses that fall in the safe region are released, and those are engineered to follow a fixed distribution that looks identical no matter what the secret key is. That is why ML-DSA’s signing loop can run several times before it produces output, and it is a security requirement, not a performance quirk.
Source: Vadim Lyubashevsky, “Lattice Signatures without Trapdoors,” Eurocrypt 2012, ePrint 2011/537; NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 13, 2024.
The short version:
- The problem it solves is key leakage. A raw lattice signature response is a blend of the secret key and randomness, and its shape depends on the secret, so publishing many of them leaks the key over time.
- The fix is reject-and-retry. The signer only publishes a candidate that falls in a safe region and otherwise restarts, which is the “aborts” in Fiat-Shamir with aborts.
- The released signatures follow a fixed distribution that is independent of the secret key, so every signer’s output looks statistically the same and reveals nothing.
- It costs some retries. ML-DSA’s signing algorithm may loop a handful of times before a candidate passes, which is a deliberate trade of a little speed for the guarantee that signatures do not leak.
- ML-DSA depends on it, which is why the standard’s signing procedure is a loop that regenerates randomness until the rejection condition is satisfied.
Picture a signer whose secret key is a slight tilt, like a table with one leg a touch short. Every time they roll a ball across the table it drifts a little in the direction of the tilt, and if you watch enough rolls you can work out exactly which leg is short and by how much. That drift is the leak. Rejection sampling is the rule that the signer only keeps a roll if it lands inside a marked circle in the center of the table, and throws away and re-rolls any that drift outside it. Because every kept roll sits inside the same circle, an observer watching only the kept rolls sees a tidy, centered pattern that betrays nothing about the tilt. The signer pays for this by re-rolling now and then, and in exchange the shape of the short leg stays hidden forever.
What problem does rejection sampling solve?
Rejection sampling solves the secret-key leakage that a lattice Fiat-Shamir signature would otherwise suffer. The signing response in these schemes has the form of the fresh per-signature randomness plus a term built from the secret key scaled by the challenge. That secret-dependent term shifts the response’s distribution away from center in a direction and magnitude tied to the secret. A single signature hides this well enough, but signatures are meant to be produced by the thousands, and across many of them the shared secret-dependent drift becomes statistically visible. An attacker collecting signatures could, without ever solving the underlying lattice problem, recover the secret key by measuring that drift.
Source: Vadim Lyubashevsky, “Lattice Signatures without Trapdoors,” Eurocrypt 2012, ePrint 2011/537.
This is a different failure mode from the ones the hard problems guard against. Module-SIS stops an attacker from forging a signature from scratch, and Module-LWE stops them from recovering the key from the public key alone. Neither of those addresses information leaking through the signatures the honest signer publishes. Rejection sampling is the piece that plugs that specific hole, which is why a secure lattice signature needs all three working together.
How does rejection sampling work in signing?
Rejection sampling works by treating each candidate signature as a lottery ticket that is only cashed if it meets a strict condition, and by re-drawing until one does. The signing loop runs like this:
- Sample fresh randomness. The signer draws a new masking value for this attempt, the equivalent of the commitment in the Fiat-Shamir scheme.
- Compute the candidate response. Combining the masking value, the hashed challenge, and the secret key produces a candidate signature, which at this point still carries the secret-dependent skew.
- Test the rejection condition. The signer checks whether the candidate falls inside the safe region, defined by norm bounds that the standard fixes so that acceptance is possible only when the secret’s influence has been masked away.
- Accept or restart. If the candidate passes, the signer outputs it. If it fails, the signer discards it entirely, including the randomness, and returns to step one with a completely fresh draw.
Source: NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 13, 2024; construction per Lyubashevsky, Eurocrypt 2012, ePrint 2011/537.
The crucial property is that a rejected candidate leaks nothing, because it is never released and the signer draws entirely new randomness on the retry rather than nudging the failed one. The parameters are tuned so the accepted candidates land in the safe region often enough that only a small expected number of retries is needed, keeping signing efficient while guaranteeing that every published signature has been filtered through the same condition.
Why does the fixed distribution keep the key hidden?
The fixed distribution keeps the key hidden because it is, by construction, the same for every possible secret key. Rejection sampling is designed so that the set of accepted signatures follows a target distribution, typically centered and secret-independent, and the acceptance test is precisely the rule that shapes the raw skewed candidates into that clean target. An attacker who collects a mountain of ML-DSA signatures sees samples from this fixed distribution and nothing else. Since the distribution does not vary with the secret, no statistical analysis of the signatures can distinguish one signer’s key from another’s, so averaging out the randomness yields no information about the key.
Source: Vadim Lyubashevsky, “Lattice Signatures without Trapdoors,” Eurocrypt 2012, ePrint 2011/537.
This is what lets the security proof reduce forgery to the hardness of Module-SIS cleanly. Because the signatures reveal nothing about the secret, the only avenue left for an attacker is to solve the hard lattice problem directly, which is the intended and studied difficulty. Without rejection sampling there would be a shortcut around the hard problem entirely, and the scheme would be broken regardless of how strong Module-SIS is. Rejection sampling is therefore not a refinement of the security, it is a precondition for the security proof to say anything at all.
How does rejection sampling fit into ML-DSA?
Rejection sampling is the “aborts” half of the Fiat-Shamir with aborts construction that ML-DSA is built on, and it is why the standard describes signing as a loop rather than a straight-line computation. The full picture stacks four ideas: the Fiat-Shamir transform removes the need for an interactive verifier, rejection sampling stops the signatures from leaking the key, Module-LWE hardness protects the signing key, and Module-SIS hardness prevents forgery. Take away any one and the scheme fails, and rejection sampling is the one that specifically addresses information leaking through legitimate use.
Source: NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 13, 2024.
There is a practical consequence worth knowing for anyone implementing or profiling ML-DSA. Because signing loops until a candidate is accepted, the time to produce a signature is not perfectly constant, it depends on how many retries a given attempt happens to need. That variability has to be handled carefully so it does not itself become a side-channel that leaks information through timing, which is one of the subtleties that makes correct ML-DSA implementation more delicate than a naive read of the algorithm suggests. This is an implementation concern that lives inside the cryptographic library, not something a migrating team configures, but it explains why using a vetted, validated implementation matters.
Common misconceptions
- “Rejection sampling is an efficiency optimization.” It is a security requirement. Without it, published signatures leak the secret key over time, so the reject-and-retry step is what makes the scheme safe, not what makes it fast.
- “A rejected signature leaks a little information.” It leaks nothing, because it is never published and the signer draws entirely fresh randomness on the retry. Only accepted signatures, which follow a fixed secret-independent distribution, ever leave the signer.
- “The retries mean ML-DSA is slow or unreliable.” The parameters are tuned so only a small expected number of retries is needed, so signing stays fast. The loop always terminates quickly in practice; it is a controlled trade of a few extra draws for the leakage guarantee.
- “Rejection sampling is what makes ML-DSA quantum-resistant.” The quantum resistance comes from the lattice hardness of Module-SIS and Module-LWE. Rejection sampling stops a separate leakage attack; it is necessary for security but it is not the source of the quantum resistance.
- “Only ML-DSA uses this.” The rejection-sampling idea, introduced by Lyubashevsky for lattice Fiat-Shamir signatures, appears across lattice signature designs. ML-DSA is the standardized one most people will meet, but the technique is general to the family.
Questions people ask
What is rejection sampling in simple terms? It is a reject-and-retry rule in signing. The signer computes a candidate signature, checks whether it falls in a safe region, and only publishes it if it does, otherwise discarding it and starting over with fresh randomness. The rule shapes every released signature into the same fixed pattern that reveals nothing about the secret key.
Why does ML-DSA reject and retry when it signs? Because the first-try response is skewed by the secret key, and publishing many skewed responses would let an attacker recover the key by statistical analysis. Rejection sampling only releases responses that fall in a safe region, which follow a distribution independent of the key, so no number of signatures leaks it.
Does rejection sampling make ML-DSA slower? Slightly, because signing may loop a few times before a candidate is accepted. The parameters are set so only a small expected number of retries is needed, so the cost is modest and the payoff is that signatures never leak the secret key.
Is rejection sampling what makes ML-DSA quantum-safe? No. The quantum safety comes from the hardness of the lattice problems Module-SIS and Module-LWE, which Shor’s algorithm does not solve. Rejection sampling defends against a different attack, the leakage of the key through published signatures, and both defenses are required.
Where does rejection sampling come from? Vadim Lyubashevsky introduced it for lattice Fiat-Shamir signatures, first in his 2009 “Fiat-Shamir with Aborts” work and refined in the 2012 “Lattice Signatures without Trapdoors.” It is the “aborts” component of the construction that ML-DSA standardized.
Do I need to worry about rejection sampling when migrating to ML-DSA? Not directly. It lives inside the cryptographic library’s signing routine, and your job is to use a validated implementation. It is worth knowing that signing time varies slightly with retries, which a good implementation handles so the variation does not become a timing side-channel.
Everything here is the map, given freely. When your team needs its post-quantum signature choices understood and validated across the estate, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.