ML-DSA
ML-DSA is NIST's main replacement for RSA and ECDSA signatures. It signs and verifies quickly, but its keys and signatures run to kilobytes: an ML-DSA-44 signature is 2,420 bytes, against 64 for Ed25519.
- Standard
- FIPS 204, August 2024, from CRYSTALS-Dilithium
- Rests on
- Module learning with errors (for the key) and module short integer solutions (for forgery), over Z8380417[X]/(X256 + 1)
- Parameter sets
- ML-DSA-44, -65 and -87, claimed at security categories 2, 3 and 5
- Sizes (ML-DSA-65)
- 1,952-byte public key, 3,309-byte signature
- Signing
- Fiat–Shamir with aborts: on average 4.25, 5.1 or 3.85 attempts per signature, depending on the parameter set
Keys
ML-DSA works in the ring Rq = Zq[X]/(X256 + 1) with q = 8,380,417 = 223 − 213 + 1. The public matrix A has k × ℓ entries in Rq and is expanded from a 32-byte seed ρ. The secret is a pair of vectors s1 and s2 with small coefficients, between −η and η, and the key is an MLWE sample:
To shorten the public key, t is split into high and low parts, t = t1·213 + t0. The public key is (ρ, t1); t0 stays in the private key. The verifier will be missing those low bits, and the signature carries a small hint that makes up for them.
Signing: Fiat–Shamir with aborts
Signing follows the Schnorr pattern of commitment, challenge and response, with one addition that is the heart of the design:
μ = H(H(pk) ‖ message)
ρ″ = H(K ‖ rnd ‖ μ) rnd: 32 fresh random bytes by default
repeat:
y ← mask vector from ρ″, coefficients below γ1
w = A·y; w1 = HighBits(w) commitment
c̃ = H(μ ‖ w1); c = SampleInBall(c̃) τ coefficients equal to ±1, the rest 0
z = y + c·s1 response
reject if ‖z‖∞ ≥ γ1 − β or ‖LowBits(w − c·s2)‖∞ ≥ γ2 − β
h = MakeHint(…) stands in for the missing t0
reject if ‖c·t0‖∞ ≥ γ2 or h has more than ω ones
signature (c̃, z, h)
An outline of FIPS 204, Algorithm 7. The rejections restart the loop with a new mask.
Why reject? The response z = y + c·s1 is the mask shifted by a secret-dependent amount. If every z were released, their distribution would drift towards c·s1, and enough signatures would reveal the key. Keeping only responses that fall in a range where every secret is equally likely to have produced them makes the distribution of z independent of s1. This is Lyubashevsky's Fiat–Shamir with aborts. The price is repetition: FIPS 204 gives the expected number of attempts as 4.25, 5.1 and 3.85 for the three parameter sets.
Verifying
The verifier recomputes the commitment from public data. Since A·z − c·t = A·y − c·s2, which differs from w only by a small term, its high bits are w1, once the hint h has corrected for the low bits of t that the public key omits:
w1' = UseHint(h, A·z − c·t1·2^13) accept if ‖z‖∞ < γ1 − β, h has at most ω ones, and c̃ = H(μ ‖ w1')
An outline of FIPS 204, Algorithm 8.
A forger who can produce a valid (c̃, z, h) without the key has solved an instance of a module short integer solution problem, in the variant Kiltz, Lyubashevsky and Schaffner call SelfTargetMSIS; their analysis also covers the quantum random-oracle model.
Parameters and sizes
| (k, ℓ) | η | τ | γ1 | γ2 | ω | Attempts | Category | |
|---|---|---|---|---|---|---|---|---|
| ML-DSA-44 | (4, 4) | 2 | 39 | 217 | (q − 1)/88 | 80 | 4.25 | 2 |
| ML-DSA-65 | (6, 5) | 4 | 49 | 219 | (q − 1)/32 | 55 | 5.1 | 3 |
| ML-DSA-87 | (8, 7) | 2 | 60 | 219 | (q − 1)/32 | 75 | 3.85 | 5 |
| Public key | Private key | Signature | |
|---|---|---|---|
| ML-DSA-44 | 1,312 | 2,560 | 2,420 |
| ML-DSA-65 | 1,952 | 4,032 | 3,309 |
| ML-DSA-87 | 2,592 | 4,896 | 4,627 |
The categories are 2, 3 and 5 rather than 1, 3 and 5: category 2 is defined by the cost of finding a SHA-256 collision rather than by key search on AES-128. The catalogue compares these sizes with the other signature schemes.
Using it
- Hedged by default. FIPS 204 mixes 32 fresh random bytes into every signature, alongside randomness derived from the key and message. The fresh randomness helps against side channels; the derived randomness protects against a faulty random-number generator. A fully deterministic variant is allowed when no randomness is available, but the standard warns against it where fault or side-channel attacks are a concern. Both produce signatures the same verifier accepts.
- Pure or pre-hash. Plain ML-DSA signs the message itself. HashML-DSA signs a hash of it, for when the message is too large to pass to the signing module; the two produce different signatures and must not be mixed up.
- Context strings. Both forms take an optional context string of up to 255 bytes, which binds a signature to its intended use.
Where it stops
ML-DSA would fall to efficient algorithms for module-LWE or module-SIS at these dimensions. As with ML-KEM, the best known attacks are lattice reduction, and security estimates depend on how that is costed. For a second signature standard on different assumptions, NIST has FIPS 205, SLH-DSA, based only on hash functions, and is evaluating further candidates, including SQIsign, in its additional-signatures process.
Primary sources
- NIST, FIPS 204: Module-Lattice-Based Digital Signature Standard (2024)
- L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler and D. Stehlé, "CRYSTALS-Dilithium: digital signatures from module lattices" (2017)
- V. Lyubashevsky, "Lattice signatures without trapdoors", EUROCRYPT 2012
- E. Kiltz, V. Lyubashevsky and C. Schaffner, "A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model", EUROCRYPT 2018
- NIST, FIPS 205: Stateless Hash-Based Digital Signature Standard (2024)