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:

t = A·s1 + s2 Recovering s1 from (A, t) is the module learning with errors problem.

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

From FIPS 204, Table 1. All three sets use q = 8,380,417 and drop d = 13 bits from t.
(k, ℓ)ητγ1γ2ωAttemptsCategory
ML-DSA-44(4, 4)239217(q − 1)/88804.252
ML-DSA-65(6, 5)449219(q − 1)/32555.13
ML-DSA-87(8, 7)260219(q − 1)/32753.855
Sizes in bytes, from FIPS 204, Table 2.
Public keyPrivate keySignature
ML-DSA-441,3122,5602,420
ML-DSA-651,9524,0323,309
ML-DSA-872,5924,8964,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

  1. NIST, FIPS 204: Module-Lattice-Based Digital Signature Standard (2024)
  2. L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler and D. Stehlé, "CRYSTALS-Dilithium: digital signatures from module lattices" (2017)
  3. V. Lyubashevsky, "Lattice signatures without trapdoors", EUROCRYPT 2012
  4. E. Kiltz, V. Lyubashevsky and C. Schaffner, "A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model", EUROCRYPT 2018
  5. NIST, FIPS 205: Stateless Hash-Based Digital Signature Standard (2024)