Rejection Sampling, or Fiat-Shamir With Aborts

The fix is due to Vadim Lyubashevsky in 2009, and it is one of those ideas that sounds like cheating until you check it.

Sometimes refuse to release the signature. Choose the refusal rule so that the values you do release are exactly uniform on a fixed range, independent of the secret.

01.The construction, in one dimension

Take the single-coordinate version again. Let $y$ be uniform on $(-\gamma, \gamma]$, let the secret contribution be $s$ with $|s| \le \beta$, and let $z = y + s$.

As the previous note showed, $z$ is uniform on $(-\gamma + s, \gamma + s]$, a box of the same width shifted by $s$. The shift is the leak.

Now add a rule:

Release $z$ only if $|z| < \gamma - \beta$. Otherwise discard everything and start again with fresh $y$.

Look at what that acceptance region is. The interval $(-\gamma + \beta,\; \gamma - \beta]$ sits entirely inside the shifted box, for every possible $s$ with $|s| \le \beta$, because the shift can move the box by at most $\beta$ in either direction.

So conditional on acceptance, $z$ is uniform on that fixed interval. Not approximately. Exactly.

And that interval does not depend on $s$. Its endpoints are $\gamma$ and $\beta$, both public parameters. An attacker looking at a million accepted values sees a million samples from a distribution that would be identical had the secret been anything else.

The shift has not been hidden or made small. It has been removed.

02.Confirming it

Rerun the simulation from the previous note with the acceptance rule added, $\gamma = 100$ and $\beta = 3$, same secret $s = 3$, same 400,000 released signatures:

$$\text{mean}(z \mid c = +1) \;=\; +0.095, \qquad \text{mean}(z \mid c = -1) \;=\; -0.145 .$$

Half the difference is $0.120$, against a true secret of $3$.

Compare with the naive version's $3.151$. The estimator has collapsed to noise around zero, and it will stay there however many signatures the attacker collects, because there is no longer a shift for it to find.

03.What it costs

Rejection is not free, and the price is restarts.

Per coordinate, the acceptance probability is the ratio of the accepted interval to the full one:

$$\frac{\gamma - \beta}{\gamma} \;=\; 1 - \frac{\beta}{\gamma} .$$

With $\gamma = 100$ and $\beta = 3$ that is $0.97$, matching the $0.9597$ observed in the simulation once both signs are accounted for.

But a real signature has many coordinates, and all of them must pass. With $N$ coordinates behaving independently, the joint acceptance probability is

$$\left(1 - \frac{\beta}{\gamma}\right)^{N},$$

which falls away quickly. ML-DSA has $\ell \cdot 256$ coordinates in $\mathbf{z}$ alone, so $N$ is in the low thousands.

Parameters are tuned so this lands somewhere around one in four to one in six. In other words, signing is expected to restart four to six times, and each restart throws away a full commitment and does the work again.

That is why the "aborts" is in the name, and it has three practical consequences worth stating plainly.

Signing is slower than verification, by roughly the expected number of attempts. This is unusual. In RSA and ECDSA the two are comparable.

Signing time is variable. The number of restarts is random, so two signatures on the same message with the same key take different amounts of time.

That variability must not depend on the secret. The number of restarts depends on $\mathbf{y}$ and on $c$, both of which are fresh per attempt, so a timing observer learns nothing about $\mathbf{s}_1$. This is a property that has to be preserved carefully, and it is why implementations are written so that the checks themselves are constant-time even though the loop count is not.

04.Why this shape and not a Gaussian

Chapter 3 described a related choice, where the standards took a centred binomial over a discrete Gaussian to avoid a side channel.

The same instinct is at work here. An earlier generation of lattice signatures used Gaussian rejection sampling, where the acceptance probability depended on a ratio of two Gaussian densities and therefore had to be computed with high-precision arithmetic per attempt. That was slow and it leaked.

ML-DSA's version uses a uniform distribution and an infinity-norm bound, so the acceptance test is a comparison of integers against a constant. No transcendental functions, no precision, no tables. It is exactly the sort of substitution that trades a little proof elegance for an implementation nobody can get subtly wrong.