Security, and the Chapter Summary

01.Two problems, not one

ML-KEM rested on Module-LWE alone. ML-DSA needs a second assumption, and the reason is the one from What a Signature Is: a signature scheme publishes values computed with the secret key, in unlimited quantity.

Module-LWE hides the secret key. Given $A$ uniform and $\mathbf{t} = A\mathbf{s}_1 + \mathbf{s}_2$ with both parts small, distinguishing $(A, \mathbf{t})$ from uniform is hard. So an attacker holding only the public key cannot extract $\mathbf{s}_1$ from it. This is the same assumption as the KEM's.

Module-SIS prevents forgery. Given $A$ uniform, finding a short non-zero $\mathbf{v}$ with

$$[\,A \,\|\, I_k\,]\,\mathbf{v} \;=\; 0$$

is hard. SIS stands for short integer solution, and the problem is to find a short vector in the kernel of a random matrix.

The connection to forgery is direct. Suppose an attacker could produce two different valid signatures on the same message under the same challenge. Both satisfy the verification equation, so subtracting them makes the message-dependent parts cancel and leaves a short non-zero element of the kernel. That is a Module-SIS solution. So forging implies solving Module-SIS, and Module-SIS is assumed hard.

Both problems reduce to worst-case approximate shortest-vector on module lattices, by results spanning Regev, Lyubashevsky, Peikert and Rosen between 2005 and 2013. So ML-DSA sits on the same foundation as ML-KEM, from Chapter 3, and neither is affected by Shor's algorithm.

02.How the two assumptions divide the work

The split is worth stating because it explains why rejection sampling is load-bearing rather than decorative.

Module-LWE covers the attacker who has the public key and nothing else.

Module-SIS covers the attacker who has the public key and arbitrarily many signatures.

The bridge between them is exactly the property Rejection Sampling, or Fiat-Shamir With Aborts established. Because each released $\mathbf{z}$ is uniform on a fixed box independent of $\mathbf{s}_1$, a signature carries no information about the secret. The security proof can therefore treat every signature query as something it could have produced itself without knowing the key, which reduces the many-signatures attacker to the no-signatures attacker, and then invokes Module-SIS at the point of forgery.

Take rejection sampling away and that bridge collapses. Signatures would leak, the proof could not simulate them, and as note 3 showed, the attack is not hypothetical.

03.Chapter summary

A digital signature is the reverse of encryption: the private key produces, the public key checks. It underwrites software updates, certificate chains and anything that must not be repudiated, and its security requirement is aggressive. An attacker may request signatures on any messages they choose and wins by forging just one on anything else.

The construction descends from Schnorr's interactive proof of knowledge, made non-interactive by the Fiat-Shamir transform, which replaces the verifier's challenge with a hash of the commitment and the message. Four pieces carry over: a commitment $\mathbf{w} = A\mathbf{y}$ from fresh randomness, a challenge $c$ hashed from it, a response $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$, and a verification equation that recomputes the commitment.

What does not carry over is Schnorr's argument that the response reveals nothing. That relied on the randomness being uniform over a group where addition wraps. Lattice randomness is bounded, so $\mathbf{z}$ is a shifted bounded distribution and the shift is the secret. A simulation with 400,000 signatures recovers a secret of $3$ as $3.15$ by taking means.

Rejection sampling fixes it. Release $\mathbf{z}$ only when $\|\mathbf{z}\|_\infty < \gamma_1 - \beta$, and the accepted values are exactly uniform on an interval that sits inside the shifted box for every possible secret. The shift is not hidden, it is gone. The same simulation then recovers $0.12$ instead of $3.15$. The price is restarting four to six times per signature, which makes signing several times more expensive than verification and variable in duration.

The challenge is sparse with $\pm 1$ coefficients so that $\beta = \tau\eta$ stays small, which is what keeps the rejection rate workable, while $\binom{256}{\tau}2^{\tau}$ possible challenges keeps it unguessable.

Two size optimisations add most of the remaining machinery. Committing to $\text{HighBits}(\mathbf{w})$ rather than $\mathbf{w}$ shrinks the challenge input, and truncating the public key to $\mathbf{t}_1$ halves it. Both make the verifier's reconstruction inexact, which is why the signer carries two further rejection checks and emits a hint vector recording the handful of coefficients that round differently.

Verification substitutes $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$ into $A\mathbf{z} - c\,2^d\mathbf{t}_1$, the $A\mathbf{s}_1$ terms cancel, and what remains is $\mathbf{w} - c\mathbf{s}_2 + c\mathbf{t}_0$. The rejection checks guarantee the first perturbation is invisible to rounding and the second moves nothing by more than one bucket, and the hint corrects the rest. So the verifier reconstructs $\mathbf{w}_1$ exactly, having never been sent $\mathbf{w}$.

The modulus is $q = 2^{23} - 2^{13} + 1$, far larger than the KEM's, because $\mathbf{y}$ alone needs nineteen bits of range. That size also gives $q - 1$ thirteen factors of two, which is why ML-DSA gets the complete negacyclic NTT that ML-KEM cannot have.

Signatures run from 2420 to 4627 bytes, thirty-eight to seventy-two times an Ed25519 signature, and that is the cost that makes signatures the awkward half of the migration.

The next chapter goes underneath all of this, to the two primitives every operation in both standards actually spends its time in: reducing a product modulo $q$, and the Keccak permutation that supplies every random byte either scheme uses.