How NIST's Post-Quantum Secure Signature ML-DSA Works

ML-DSA (Module-Lattice Digital Signature Algorithm) is NIST's standardized post-quantum digital signature scheme, published as FIPS 204 in August 2024. It is the official name for the algorithm formerly known as CRYSTALS-Dilithium.

Replacement for Classical Signatures

Classical signatures (RSA, ECDSA, EdDSA) rely on integer factorization and discrete logarithms — problems that quantum computers solve efficiently via Shor's algorithm. ML-DSA instead relies on Module-LWE and Module-SIS — lattice problems for which no efficient quantum algorithm is known. The "module" structure (polynomial rings over finite fields) keeps keys and signatures practical while preserving strong security assumptions.

Sizes and Performance

Key and signature sizes are from FIPS204, Table 2 (p. 16). Security categories are from FIPS204, Table 1 (p. 15).

Compared to classical schemes:

ML-DSA keys and signatures are much larger — the main practical cost of post-quantum migration. Signing is also slower than Ed25519 due to polynomial arithmetic and rejection sampling, though verification is reasonably fast (especially with AVX2/NEON optimizations).

Mathematical Foundation

ML-DSA operates in the polynomial ring FIPS204, §2.4.1 (p. 7):

$$R_q={\mathbb{Z}}_q[X]/(X^n+1)$$

where $n=256$ and $q=8380417$ FIPS204, §2.3 (p. 5). The prime satisfies $q\equiv 1(\mathrm{mod}2n)$, enabling the Number Theoretic Transform for fast polynomial multiplication FIPS204, §2.5; §7.5 (pp. 8, 42).

Vectors of $k$ or $\ell$ polynomials from $R_q$ form the module structure FIPS204, §2.4.2 (p. 7). The security parameters are FIPS204, Table 1 (p. 15; see also §6.1 and §6.2):

These map to NIST security categories 2, 3, and 5 respectively FIPS204, Table 1 NISTCAT. Category 2 is defined against SHA-256 collision resistance (~128-bit, collision context); categories 3 and 5 are defined against AES-192 and AES-256 key search (~192-bit and ~256-bit).

Keys

Secret key

The secret key consists of FIPS204, §6.1:

• ${\mathbf{s}}_1\in R_q^{\ell }$ and ${\mathbf{s}}_2\in R_q^k$: short polynomial vectors with coefficients in $[-\eta ,\eta ]$
• ${\mathbf{t}}_0$: the dropped low-order bits of the public-key vector $\mathbf{t}$
• $\rho$: public seed (also in the public key)
• $K$: private seed for signing randomness
• $\mathrm{tr}$: hash of the public key, used when forming $\mu$

Public key

The public key is derived via a Module-LWE relationship:

1. Sample a random matrix $\mathbf{A}\in R_q^{k\times \ell }$ from seed $\rho$ (expanded on the fly, not stored).
2. Compute $\mathbf{t}=\mathbf{A}{\mathbf{s}}_1+{\mathbf{s}}_2$.
3. Split $\mathbf{t}$ into high and low parts: $({\mathbf{t}}_1,{\mathbf{t}}_0)=Power2Round(\mathbf{t})$, dropping $d=13$ low-order bits per coefficient.

The public key is $(\rho ,{\mathbf{t}}_1)$. Finding ${\mathbf{s}}_1,{\mathbf{s}}_2$ from $\mathbf{A}$ and $\mathbf{t}$ is a Module-LWE problem — believed hard even for quantum computers.

Signing

Signing is a Fiat–Shamir with aborts protocol FIPS204, §3.3. In the interactive version, the prover commits to a random value, the verifier sends a challenge, and the prover responds. ML-DSA makes this non-interactive by deriving the challenge from a hash of the commitment and message — and adds rejection sampling so the response does not leak the secret key.

Before the commit/challenge loop, the signer computes a message representative (this binds the signature to both the message and the public key):

$$\mu =H(\text{tr}\Vert M,64\text{ bytes})$$

where $\mathrm{tr}=H(\mathrm{pk},64)$ is a hash of the public key FIPS204, Algorithm 7, line 6.

Phase 1: Commit

The goal of the commit phase is to pick a random masking vector $\mathbf{y}$, publish a compressed commitment to $\mathbf{w}=\mathbf{Ay}$, and bind it to the message via a hash. The full vector $\mathbf{w}$ is never included in the signature.

Step 1 — Sample the mask. Draw a random vector $\mathbf{y}\in R_q^{\ell }$ with coefficients in $[-{\gamma }_1+1,{\gamma }_1]$.

Step 2 — Compute the commitment. $\mathbf{w}=\mathbf{Ay}$.

Step 3 — Round to high bits. Each coefficient $r$ of $\mathbf{w}$ is decomposed mod $q$ into a coarse part and a fine part:

$$r\equiv r_1\cdot 2{\gamma }_2+r_0(\mathrm{mod}q),|r_0|<2{\gamma }_2$$

The commitment is ${\mathbf{w}}_1=\mathrm{HighBits}(\mathbf{w})$, which keeps only $r_1$ from each coefficient — effectively rounding $r$ to the nearest multiple of $2{\gamma }_2$. The fine part $r_0$ is discarded.

Think of each coefficient as a number on a line divided into buckets of width $2{\gamma }_2$. The commitment records only which bucket each coefficient falls in, not its exact position within the bucket.

How many bits enter the hash? Each bucket index $r_1$ is small enough to encode in 6 bits (ML-DSA-44) or 4 bits (ML-DSA-65 and ML-DSA-87) FIPS204, Algorithm 28. The $\approx 18$ lower-order bits within each bucket are thrown away. This is why the signature can store a hash of ${\mathbf{w}}_1$ rather than the full $\mathbf{w}$.

Step 4 — Hash the commitment. Encode ${\mathbf{w}}_1$ and hash it together with $\mu$:

$$\tilde{c}=H(\mu \Vert \text{w1Encode}({\mathbf{w}}_1),\lambda /4\text{ bytes})$$

The output $\tilde{c}$ is the commitment hash (64 bytes for ML-DSA-65). It is stored in the signature. At this point the signer has publicly committed to ${\mathbf{w}}_1$ and bound it to the message — but has not yet produced the response.

Phase 2: Challenge

The challenge is a sparse polynomial $c\in R_q$ with exactly $\tau$ coefficients equal to $\pm 1$ and the rest zero (e.g., $\tau =49$ for ML-DSA-65). It is not stored in the signature. Instead, both signer and verifier derive it deterministically from $\tilde{c}$:

$$c=\text{SampleInBall}(\tilde{c})$$

SampleInBall uses $\tilde{c}$ as a seed to pseudorandomly place $\tau$ nonzero $\pm 1$ coefficients among the 256 positions FIPS204, Algorithm 29. Because $\tilde{c}$ depends on both ${\mathbf{w}}_1$ and $\mu$, the challenge is bound to the commitment and the message. An adversary who tries to reuse a response $\mathbf{z}$ for a different message will derive a different $c$ and fail verification.

Phase 3: Response

Given the challenge $c$, the signer computes:

$$\mathbf{z}=\mathbf{y}+c\cdot {\mathbf{s}}_1$$

Because $\mathbf{w}=\mathbf{Ay}$ and $\mathbf{t}=\mathbf{A}{\mathbf{s}}_1+{\mathbf{s}}_2$, it follows that $\mathbf{Az}-c\cdot \mathbf{t}\approx \mathbf{w}$ — the response links back to the original commitment. The signer also computes the hint $\mathbf{h}$ (Phase 4 below).

Phase 4: The hint

The hint solves a practical problem: the verifier must reconstruct ${\mathbf{w}}_1$ from the signature and compressed public key, but two sources of error make naive rounding unreliable.

Problem 1 — Compressed public key. The public key stores ${\mathbf{t}}_1$, not full $\mathbf{t}$. The $d=13$ low-order bits of each coefficient were dropped during key generation FIPS204, §6.1. The verifier computes:

$${\mathbf{w}}_{\mathrm{approx}}^{\prime }=\mathbf{Az}-c\cdot {\mathbf{t}}_1\cdot 2^d$$

This is close to $\mathbf{w}$ but not exact — the missing bits of $\mathbf{t}$ introduce small errors.

Problem 2 — Rounding ambiguity. ${\mathbf{w}}_1$ records which bucket each coefficient falls in (multiples of $2{\gamma }_2$). When a value sits near a bucket boundary, a small error from Problem 1 can push it into the adjacent bucket — giving the verifier the wrong ${\mathbf{w}}_1^{\prime }$ and causing the hash check to fail.

The fix. For each coefficient, the signer records a single hint bit:

$$h=0\text{ if }\mathrm{HighBits}(r)=\mathrm{HighBits}(r+z),\text{else }h=1.$$

During verification, UseHint adjusts the bucket index at every position where $h=1$, correcting the rounding FIPS204, Algorithms 39–40. The hint $\mathbf{h}$ is a binary vector in $R_2^k$ (one bit per coefficient across the $k$ polynomials). At most $\omega$ bits are set to 1 per signature ($\omega =80$ for ML-DSA-44, $55$ for ML-DSA-65, $75$ for ML-DSA-87) FIPS204, Table 1.

Analogy: Suppose you round several measurements to the nearest integer, but your colleague only sees noisy versions. For measurements near $2.5$ or $3.5$, they might round the wrong way. The hint is a list of flags saying "I rounded up here" or "I rounded down here" — just for the ambiguous cases.

Phase 5: Rejection sampling

If any check fails, the signer aborts and restarts from Phase 1 with a fresh $\mathbf{y}$. There are two stages FIPS204, Algorithm 7.

Stage 1 — abort if either norm is too large:

$$\Vert \mathbf{z}{\Vert }_{\infty }\ge {\gamma }_1-\beta \text{or}\Vert {\mathbf{r}}_0{\Vert }_{\infty }\ge {\gamma }_2-\beta$$

where

$${\mathbf{r}}_0=\mathrm{LowBits}(\mathbf{Ay}-c\cdot {\mathbf{s}}_2),\beta =\tau \eta .$$

Stage 2 — abort if either condition holds:

$$\Vert c\cdot {\mathbf{t}}_0{\Vert }_{\infty }\ge {\gamma }_2\text{or}\mathrm{wt}(\mathbf{h})>\omega$$

Here $\mathrm{wt}(\mathbf{h})$ is the Hamming weight of the hint vector (the number of coefficients with hint bit set to 1).

Expected number of restarts: 4.25 (ML-DSA-44), 5.1 (ML-DSA-65), 3.85 (ML-DSA-87) FIPS204, Table 1.

Why Stage 1 checks z. The response is a shift of the mask $\mathbf{y}$:

$$\mathbf{z}=\mathbf{y}+c\cdot {\mathbf{s}}_1.$$

Without rejection, that shift would push coefficients across the boundary of y's original range, and the published distribution of z would leak s₁.

Why Stage 1 checks r₀. The same boundary argument applies to s₂. After the challenge is known, the signer forms

$${\mathbf{r}}_0=\mathrm{LowBits}(\mathbf{Ay}-c\cdot {\mathbf{s}}_2)=\mathrm{LowBits}(\mathbf{w}-c\cdot {\mathbf{s}}_2).$$

The term c·s₂ shifts Ay. Coefficients that already sit near a rounding-bucket edge can be pushed across the boundary of the accepted low-bit region. If those overflows were published, an observer could tell which way the shift went — and that leaks s₂. Rejection sampling keeps only those r₀ that remain strictly inside the safe interior, so the observed low bits no longer depend on s₂.

Why Stage 2 checks ‖c · t₀‖∞. These checks are not the same as the r₀ rejection: they control how the verifier reconstructs high bits from a compressed public key. The public vector is decomposed as

$$\mathbf{t}=\mathbf{A}{\mathbf{s}}_1+{\mathbf{s}}_2={\mathbf{t}}_1\cdot 2^d+{\mathbf{t}}_0.$$

The verifier receives only t₁. Using w = Ay and z = y + c·s₁,

$$\mathbf{Az}-c\cdot \mathbf{t}=\mathbf{Ay}-c\cdot {\mathbf{s}}_2.$$

The verifier cannot form this exactly: it computes

$$\mathbf{Az}-c\cdot {\mathbf{t}}_1\cdot 2^d,$$

so the missing term is c·t₀. That correction must stay small. If

$$\Vert c\cdot {\mathbf{t}}_0{\Vert }_{\infty }\ge {\gamma }_2,$$

it can cross too many rounding-bucket boundaries, and both the number and the locations of hints start to depend on the secret-dependent t₀. Requiring

$$\Vert c\cdot {\mathbf{t}}_0{\Vert }_{\infty }<{\gamma }_2$$

keeps the correction inside a single-bucket range.

Why Stage 2 checks wt(h). The hint h is part of the signature, so it is public. A bit hᵢ = 1 means: for this coefficient, use the neighboring high-bit value — a rounding boundary was crossed. If wt(h) > ω, the signature would reveal too much about that rounding behavior. ML-DSA therefore caps the number of 1-bits at a public bound ω and restarts when the cap is exceeded.

Phase 6: Output

The signature is the triple $(\tilde{c},\mathbf{z},\mathbf{h})$ — the commitment hash, response, and hint. The sparse challenge $c$ is not stored; the verifier re-derives it from $\tilde{c}$.

Verification

Given public key $(\rho ,{\mathbf{t}}_1)$, message $M$, and signature $(\tilde{c},\mathbf{z},\mathbf{h})$:

1. Recompute $\mu =H(\mathrm{tr}\Vert M)$ and derive $c=\mathrm{SampleInBall}(\tilde{c})$.
2. Reconstruct the approximate commitment:

$${\mathbf{w}}_{\mathrm{approx}}^{\prime }=\mathbf{Az}-c\cdot {\mathbf{t}}_1\cdot 2^d$$

3. Apply the hint:

$${\mathbf{w}}_1^{\prime }=\mathrm{UseHint}(\mathbf{h},{\mathbf{w}}_{\mathrm{approx}}^{\prime })$$

4. Recompute ${\tilde{c}}^{\prime }=H(\mu \Vert w1Encode({\mathbf{w}}_1^{\prime }))$.
5. Accept if $\tilde{c}={\tilde{c}}^{\prime }$ and $\Vert \mathbf{z}{\Vert }_{\infty }<{\gamma }_1-\beta$.

ML-DSA in a Glance

Why Rejection Sampling and Bit Dropping?

FIPS204, §3.3, p. 10 explains both design choices by starting with a simplified interactive protocol. Understanding this toy version makes the full ML-DSA signing flow much clearer.

The basic interactive protocol

Imagine a prover who knows short secret matrices ${\mathbf{S}}_1$ and ${\mathbf{S}}_2$, and a verifier who knows $\mathbf{A}$ and $\mathbf{T}=\mathbf{A}{\mathbf{S}}_1+{\mathbf{S}}_2$. The prover wants to convince the verifier that it knows ${\mathbf{S}}_1$ and ${\mathbf{S}}_2$ without revealing them:

1. Commitment. The prover picks random short vectors $\mathbf{y}$ and ${\mathbf{y}}_2$ and sends:

$${\mathbf{w}}_{\mathrm{Approx}}=\mathbf{Ay}+{\mathbf{y}}_2$$

2. Challenge. The verifier sends a short challenge vector $\mathbf{c}$.
3. Response. The prover returns $\mathbf{z}=\mathbf{y}+{\mathbf{S}}_1\mathbf{c}$. The verifier checks that $\mathbf{z}$ is short and that:

$$\mathbf{Az}-\mathbf{Tc}\approx {\mathbf{w}}_{\mathrm{Approx}}$$

ML-DSA is this protocol made non-interactive (the challenge comes from a hash) and compressed (polynomial modules instead of big integer matrices). But the logic is the same.

A scalar example: why rejection sampling is needed

FIPS204, §3.3 states the flaw directly: without rejection sampling, the response $\mathbf{z}$ is biased in a direction related to ${\mathbf{s}}_1$. The same is true of ${\mathbf{r}}_0=\mathrm{LowBits}(\mathbf{Ay}-c\cdot {\mathbf{s}}_2)$, which is biased in a direction related to ${\mathbf{s}}_2$. The problem is not that an adversary can algebraically solve for the secret — the coefficients are small and the random masks dominate. The problem is that the probability distribution of published values shifts toward the secret, especially when a shift crosses the boundary of the accepted region.

Strip everything down to one dimension. Suppose the secret is $s_1=3$, the challenge is $c=+1$, and the prover picks a random mask $y$ uniformly from $\{0,1,\dots ,99\}$. The response is:

$$z=y+s_1\cdot c=y+3$$

If there were no secret ($s_1=0$), $z$ would be uniform on $\{0,\dots ,99\}$. With $s_1=3$, the distribution of $z$ is uniform on $\{3,\dots ,102\}$ — the same shape, but shifted three units to the right. An adversary who collects many responses does not need to solve a linear system; it can detect that the histogram of $z$ values is centered around a value that depends on $s_1$ rather than looking like uniform random noise.

In the full scheme, $c$ varies per signature (derived from a hash), so the shift direction changes. But the distribution of $\mathbf{z}$ is still correlated with ${\mathbf{s}}_1$ — the outputs cluster in a way that reveals information about the secret direction.

The same leak exists for ${\mathbf{s}}_2$, through the low bits of the shifted commitment FIPS204, §3.3:

$${\mathbf{r}}_0=\mathrm{LowBits}(\mathbf{Ay}-c\cdot {\mathbf{s}}_2).$$

Here $\mathbf{Ay}-c\cdot {\mathbf{s}}_2$ is $\mathbf{Ay}$ shifted by $c\cdot {\mathbf{s}}_2$. Coefficients near a rounding-bucket edge can be pushed across the boundary of the accepted region

$$\Vert {\mathbf{r}}_0{\Vert }_{\infty }<{\gamma }_2-\beta .$$

Those crossings are not random: they happen in the direction of ${\mathbf{s}}_2$. Publishing them would leak ${\mathbf{s}}_2$.

Rejection sampling fixes both leaks. As with Schnorr signatures, the signer derives the challenge from a hash of the commitment and message. It then aborts and restarts with a fresh $\mathbf{y}$ unless both $\mathbf{z}$ and ${\mathbf{r}}_0$ lie strictly inside their accepted regions (the Stage 1 checks in Phase 5). Only those transcripts are published, so their distribution is independent of ${\mathbf{s}}_1$ and ${\mathbf{s}}_2$.

A scalar example: why lower-order bits are removed

The bit-dropping optimizations serve a different goal: smaller keys and signatures, not security against bias.

Suppose a commitment coefficient is $w=73,842$. ML-DSA does not store or transmit this full value. Instead it divides the number line into buckets of width $2{\gamma }_2$ and records only the bucket index:

$$w=\underset{w_1}{\underbrace{73}}\times 1000+\underset{w_0}{\underbrace{842}}$$

Only $w_1=73$ (a few bits) goes into the hash that forms the challenge. The lower part $w_0=842$ (roughly 10 bits) is discarded. The signature stores a hash of $w_1$, not the full $w$ — saving hundreds of bytes across all coefficients.

The public key uses the same trick. If $\mathbf{t}=\mathbf{A}{\mathbf{s}}_1+{\mathbf{s}}_2$ has a coefficient $t=5,291,307$, ML-DSA drops the $d=13$ low-order bits and publishes only the high part $t_1$. The verifier works with this compressed value and the hint (Phase 4 above) to recover the correct rounding when the approximation is ambiguous.

Without bit dropping, ML-DSA signatures and public keys would be substantially larger. Without hints, the verifier could not reliably recover the signer's bucket choices from the compressed values. Without rejection sampling, the responses would leak the secret key. All three mechanisms work together FIPS204, §3.3.

Internal Hash Functions

FIPS204 specifies two hash functions used throughout the scheme:

• SHAKE-128: expands seeds to generate the matrix $\mathbf{A}$ and masking vector $\mathbf{y}$
• SHAKE-256: hashes the public key, forms the message representative $\mu$, and computes the commitment hash $\tilde{c}$

Security Assumptions

ML-DSA's security reduces to:

1. Module-LWE: Given $\mathbf{A}$ and $\mathbf{t}=\mathbf{A}{\mathbf{s}}_1+{\mathbf{s}}_2$ for short secrets, distinguish $\mathbf{t}$ from uniform.
2. Module-SIS: Find a short nonzero vector $\mathbf{z}$ such that $\mathbf{Az}=0$.

Both are believed hard against classical and quantum adversaries. No significant cryptanalytic breaks have been found against the full parameter sets since Dilithium's introduction in 2017.

Threshold ML-DSA

Standard ML-DSA assumes a single party holds the secret key. Threshold signing distributes that key across $n$ parties so that any $t$ of them can collaborate to produce a valid signature, but fewer than $t$ learn nothing about the key.

This is harder for ML-DSA than for classical schemes because:

• The secret is a vector of short polynomials, not a scalar
• Rejection sampling must be coordinated across parties without leaking shares
• The Fiat–Shamir structure requires secure multi-party computation for the response step

Threshold ML-DSA is an active research and engineering area — relevant for custodial wallets, HSM clusters, and any system where single-key compromise is unacceptable. We will discuss about the recent advancements in Threshold ML-DSA in the next blog.

---