Ml Dsa Dilithium Design Rejection Sampling

Short answer: CRYSTALS-Dilithium is a lattice-based signature scheme built on the "Fiat-Shamir with Aborts" approach. The signer draws a random masking vector, computes a candidate signature, and restarts if the candidate could reveal information about the secret key. This rejection step is what lets a signature be published without leaking the key. NIST approved FIPS 204 (ML-DSA), which is derived from Dilithium, on 13 August 2024.

The design idea

The Dilithium specification says the scheme is based on the "Fiat-Shamir with Aborts" approach and bears most resemblance to earlier lattice schemes by Guneysu, Lyubashevsky and Poppelmann (GLP12) and Bai and Galbraith (BG14). The authors present a simplified, less efficient version in the specification to help readers unfamiliar with the framework. That version is essentially a slightly modified form of the Bai-Galbraith scheme.

Key generation

Key generation samples a public matrix A and secret vectors s1 and s2 whose coefficients are small, of size at most a parameter called eta. The public key includes t = A s1 + s2, with all arithmetic over a polynomial ring. In the specification's description the ring modulus is 2^23 - 2^13 + 1 and polynomials have 256 coefficients.

Signing and the abort

The signing algorithm generates a masking vector y with coefficients below a bound called gamma1. The specification says this parameter is set strategically: large enough that the signature does not reveal the secret key, yet small enough that the signature is not easily forged. The signer computes A y and keeps the high-order bits, called w1. A challenge c is made by hashing the message together with w1. In the version the specification describes, c is a polynomial with exactly 60 coefficients of plus or minus one and the rest zero. It has small norm and comes from a domain larger than 2^256. The candidate signature is z = y + c s1.

If z were output directly, it could leak information about the secret key. The specification's pseudocode therefore includes a rejection test. If the largest coefficient of z is at least gamma1 minus beta, or the low-order bits of A y minus c s2 are too large, z is set to a failure value and the loop runs again with a fresh y. The signature is the pair (z, c). A verifier recomputes the high bits from A z minus c t and checks them against the challenge and the size bound.

Round 3 specification

The Round 3 specification keeps the same framework. It refers to a parameter tau for the number of plus or minus one entries in c rather than fixing it at 60, and says the challenge domain size should be between 128 and 256 bits.

What this does not tell you

The specifications describe the design and its parameters. They do not report speed or size figures in the passages used here, and this post does not compare Dilithium to other signature schemes. Whether any particular product uses ML-DSA is outside what these documents cover. Final ML-DSA in FIPS 204 can differ from the Round 3 Dilithium text, so check the standard for exact parameters.

FAQ

What does "Fiat-Shamir with Aborts" mean?

A signing approach where the signer restarts if a candidate signature could leak information about the secret key.

Why reject some candidates?

So the published signature does not reveal the secret key, per the Dilithium specification.

What is in the public key?

A matrix A and t = A s1 + s2, where s1 and s2 are secret vectors with small coefficients.

How does the challenge work?

It is a hash of the message and the high-order bits of A y, mapped to a sparse polynomial with entries of plus or minus one.

Is Dilithium the same as ML-DSA?

ML-DSA in FIPS 204 is derived from Dilithium. Details can differ, so use the standard for implementations.