Ciphers · Post-quantum
The ML-DSA signature algorithm
How ML-DSA (FIPS 204, from Dilithium) signs with lattices and retries until the signature leaks nothing, and what its sizes mean.
ML-DSA, the Module-Lattice-Based Digital Signature Algorithm, is the post-quantum replacement for RSA and elliptic-curve signatures. NIST published it as FIPS 204 on 13 August 2024, derived from CRYSTALS-Dilithium. A signature proves that a message came from the holder of a private key and hasn't been changed. The signatures that vouch for websites, software updates and documents today (RSA, ECDSA and EdDSA) would all fall to Shor's algorithm. ML-DSA's security rests on lattice problems, module-LWE and module-SIS (short integer solution), which aren't known to be vulnerable to quantum computers.
What a signature scheme does
There are three operations. Key generation makes a private signing key and a public verification key. Signing takes the private key and a message and produces a signature. Verifying takes the public key, the message and the signature, and says yes or no. Anyone can verify, and only the key holder can sign. The classical examples on this site are RSA and the ElGamal signature. Signatures are also what authenticates the key exchange in Diffie-Hellman and in ML-KEM, which on their own prove nothing about who's at the other end.
How ML-DSA signs
ML-DSA uses the structure of Fiat–Shamir with aborts, and the idea can be told without the lattice detail:
- The public key is a set of noisy equations, as in ML-KEM, and the secret is the short solution. A signature is a short vector that satisfies a related equation, which only someone who knows the secret can produce.
- The signer picks a fresh random mask, computes a commitment from it, and hashes the commitment together with the message to get a challenge, a sparse polynomial with a few ±1 coefficients. This turns an interactive proof into a signature, the Fiat–Shamir transform.
- The response is the mask plus the challenge times the secret. A response of that shape could leak the secret if it were seen often enough, so the signer checks that it falls inside a safe range, and if not throws it away and starts again with a new mask. That's the "abort". It takes a few attempts on average, and no abort is ever visible in the output.
- The verifier recomputes the commitment from the public key and the signature, hashes it with the message, and checks that it gets the same challenge and that the response is short.
The arithmetic uses polynomials of 256 coefficients modulo the prime q = 8,380,417 (223 − 213 + 1). Signing is fast, and the price is in the sizes.
Sizes
| Scheme | Public key | Signature |
|---|---|---|
| Ed25519 (classical) | 32 bytes | 64 bytes |
| RSA-2048 (classical) | 256 bytes (modulus) | 256 bytes |
| ML-DSA-44 (NIST category 2) | 1,312 bytes | 2,420 bytes |
| ML-DSA-65 (category 3) | 1,952 bytes | 3,309 bytes |
| ML-DSA-87 (category 5) | 2,592 bytes | 4,627 bytes |
An ML-DSA signature is 38 to 72 times the size of an Ed25519 one. That matters for protocols that send a chain of signatures, such as a TLS certificate chain, and it's the main reason signatures are migrating more slowly than key exchange. The private key is stored as a 32-byte seed, and the expanded forms are 2,560 to 4,896 bytes.
The other signature standards
- SLH-DSA (FIPS 205, from SPHINCS+) is built only from hash functions. Its security assumption is the most conservative of all, since any signature scheme needs a good hash anyway, but its signatures are much larger and signing is slower. NIST describes it as the backup in case the lattice schemes are ever found to be flawed.
- FN-DSA (from FALCON, to be FIPS 206) also uses lattices, with smaller signatures than ML-DSA but a more delicate implementation that depends on floating-point arithmetic. NIST has listed it as in development.
Where signatures are used, and why the size matters there
A signature is checked far more often than it's made, so verification speed matters as much as signing speed. A web connection can carry several signatures at once: the server's proof that it holds its key, plus the certificates that vouch for that key, each signed by the one above it. With Ed25519-sized signatures that costs a few hundred bytes. With ML-DSA-65 every signature and every public key in the chain adds about three and two kilobytes, so a handshake that carried a few hundred bytes of signature data now carries ten kilobytes or more. The same holds for signed software updates, signed documents and tokens. ML-DSA already has a standard encoding for JSON and CBOR web tokens (RFC 9964), and an SSH draft adds it for that protocol. Where the size is a problem, the options are FN-DSA's smaller signatures or a redesign of the protocol.
Caveats
- Randomness and secrets. As with every signature scheme, leaking the per-signature mask reveals the private key. ML-DSA offers a deterministic mode and a hedged mode, which mixes fresh randomness with the key and the message as protection against both bad random numbers and fault attacks.
- Hybrids. Many deployments pair ML-DSA with a classical signature for now, so a flaw in either one alone doesn't let anyone forge.
- Size and speed on small devices are the practical hurdles, not the maths.
- Don't use the toy code from this site for anything real. The lattice example on the ML-KEM page shows the problem, and a signature scheme needs reviewed code.
Common questions
Is ML-DSA the same as Dilithium?
ML-DSA is the NIST standard derived from CRYSTALS-Dilithium, with changes, so the two aren't interoperable.
Why are the signatures so big?
A lattice signature is a vector of many small numbers, and that doesn't compress as well as a single elliptic-curve point.
Do I need post-quantum signatures right now?
Less urgently than a post-quantum key exchange. A forged signature has to be made while it matters, whereas a recorded key exchange can be broken years later.
What does cipher.ink sign?
Nothing. Messages are sealed with AES-GCM, which authenticates them with its built-in tag, so no public-key signatures are involved.