CRYSTALS-Dilithium (ML-DSA)

Introduction

CRYSTALS-Dilithium, standardized by NIST as ML-DSA (Module-Lattice-Based Digital Signature Algorithm, FIPS 204), is the primary post-quantum replacement for RSA and ECDSA signatures. It is the lattice-based sibling of CRYSTALS-Kyber and shares much of the same mathematical foundation.

What makes lattice signatures tricky isn’t the math of signing itself — it’s that a naive approach leaks a tiny fraction of the secret key with every signature produced. Given enough signatures, an attacker could reconstruct the key entirely. Dilithium’s answer, called Fiat-Shamir with Aborts, is paradoxically simple: after producing a candidate signature, check whether it happens to reveal too much. If it does, reject and resample with fresh randomness, repeating until you get a signature that’s provably safe to publish.

ML-DSA defines three standardized parameter sets (ML-DSA-44, ML-DSA-65, and ML-DSA-87, corresponding to NIST security levels 2, 3, and 5), which scale the matrix dimensions and parameters to offer varying levels of security and performance.

Table of Contents

• The Leakage Problem
• High-Level Overview
• Key Generation
• Signing (with Aborts)
• Interactive Visualizer
• A Worked Example
• Verification (and the Role of Hint Bits)
• Why Rejection Sampling Preserves Security
• FAQ
• References

The Leakage Problem

A signature scheme built directly on lattices has an awkward property: the signature z = y + c·s (masking randomness y, plus challenge c times secret key s) has a distribution that’s subtly shaped by the secret s. Values near the edge of the allowed range are systematically less likely if s pushed them there. An attacker collecting enough signatures can, in principle, use that statistical shaping to reconstruct s.

Fiat-Shamir with Aborts (Lyubashevsky, 2009) closes this leak: instead of always using whatever y you sampled, you only accept the signature if the resulting z falls in a safe zone far from the boundary — a zone where the influence of s cannot be statistically detected. If z lands too close to the edge, you discard the attempt and sign again.

The security of this scheme relies on two foundational hardness assumptions: Module-LWE (Module Learning With Errors) for key generation and public-key security, and Module-SIS (Module Short Integer Solution) for unforgeability.

High-Level Overview

Before diving into the exact math, here is how the pieces fit together:

1. KeyGen: Create a public matrix A from a seed, generate small secret vectors s₁ and s₂, and compute a public key t (where t ≈ A·s₁).
2. Sign: Guess a masking vector y, hash it with the message to create a challenge c, and compute a signature z = y + c·s₁. If z or related values are too large, abort and try again. Generate hint bits to help the verifier.
3. Verify: Use z, c, and the hint bits to reconstruct the hash input, re-derive the challenge, and ensure it matches c.

Key Generation

1. Generate a public k×l matrix A of polynomials in the ring ℤ_q[x]/(xⁿ+1) from a short public seed.
2. Sample small secret vectors s₁ (length l) and s₂ (length k), with coefficients bounded by a small constant η.
3. Compute the public key: t = A·s₁ + s₂ (mod q) — a genuine Module-LWE public key, structurally identical to Kyber’s. Because A is derived from a seed, the public key is essentially just (t, seed), keeping it highly compact.
4. The private key is (s₁, s₂).

Signing (with Aborts)

To sign a message, the signer enters a loop, repeating until a candidate passes the main bound on z, alongside secondary checks on low-order bits and hint limits:

1. Sample a fresh masking vector y, coefficients uniform in a wide range [-(γ₁-1), γ₁].
2. Compute w = A·y (mod q), then keep only its high-order bits w₁ (the low-order bits are discarded — they carry no information the verifier needs, and dropping them keeps signatures compact).
3. Derive the challenge c — a small polynomial deterministically hashed from the message and w₁: c = H(message, w₁).
4. Compute z = y + c·s₁.
5. Bound Checks (the “aborts”): If any coefficient of z falls outside the safe range [-(γ₁-β), γ₁-β] (leaving room for c·s₁), discard the attempt. In addition to this primary bound, the full scheme also rejects if the low-order bits of r = A·z - c·t are too large (to ensure the high bits remain recoverable), or if the number of required hint bits exceeds a standardized limit ω. If any check fails, go back to step 1 with a fresh y. This acts exactly like rejection sampling that forces the output to look as if it came from a secret-independent distribution.
6. Once all checks pass, compute the hint bits and output the signature (z, c, hint).

Interactive Visualizer

Real ML-DSA uses n=256 and a modulus q = 2²³ - 2¹³ + 1 = 8380417, with a challenge polynomial of Hamming weight τ (a “ball” of ±1 coefficients scattered among 256 positions — an astronomically large challenge space).

The visualizer above implements the identical structure — Module-LWE keys, the abort loop, and genuine Decompose / MakeHint / UseHint functions lifted straight from the ML-DSA specification — but at n=4, q=8192. Note: These toy parameters are completely insecure and exist only for illustration, small enough to watch a rejection happen and see exactly which values triggered it.

A Worked Example

Using the visualizer’s toy parameters, signing typically takes 1-3 attempts before a candidate survives the rejection loop. You can see this directly in the “attempts” counter:

1. Attempt 1: A masking vector y produces w = A·y; its high bits (w₁) get hashed together with the message to produce challenge c. The candidate signature z = y + c·s₁ is computed and checked. A coefficient in z exceeds the γ₁-β bound, so the entire attempt (y, w, c, z) is discarded.
2. Attempt 2: A fresh y is sampled and the process repeats. This time, z lands safely inside the boundary. The secondary low-order bounds and hint limits also pass.
3. Hints & Output: Hint bits are computed from c·s₂ so the verifier can reconstruct w₁ from A·z - c·t alone. The signature is published.

Verification (and the Role of Hint Bits)

The verifier doesn’t have w — only (z, c, hint) and the public key. To verify, they recompute a noisy approximation of w:

r′ = A·z − c·t = A·(y + c·s₁) − c·(A·s₁ + s₂) = A·y − c·s₂ = w − c·s₂ (mod q)

So r′ is close to w, but perturbed by the small term c·s₂ — close enough that the high bits usually match, but not always (specifically, right at rounding boundaries).

In essence, the verifier recovers a noisy version of w and uses the hint to correct the rounding errors. The hint bits, computed by the signer (who knows w exactly), tell the verifier exactly which coefficients need a ±1 nudge to recover the true w₁ from r′. Once w₁ is recovered, the verifier recomputes the challenge hash c′ = H(message, w₁) and accepts the signature if c′ = c.

Why Rejection Sampling Preserves Security

The deep result behind Fiat-Shamir with Aborts is that conditioned on being accepted, the distribution of z is statistically independent of which secret s₁ was used. It looks exactly like it would if y had been sampled from the safe zone directly, with no boundary effects to leak information about s₁.

This is why the “abort” isn’t a failure or a workaround — it’s the core mathematical mechanism that makes each individual published signature information-theoretically safe, no matter how many millions of signatures an attacker collects.

FAQ

Why does Dilithium use uniform sampling for y instead of discrete Gaussians?

Older lattice schemes often sampled randomness from a Gaussian (bell-curve) distribution because it provided tighter mathematical bounds. However, sampling discrete Gaussians securely in hardware is notoriously difficult and prone to side-channel attacks. ML-DSA uses uniform sampling (picking numbers evenly from a flat range) which is drastically simpler to implement securely and in constant time, even if it requires slightly larger parameters to achieve the same security.

Does ML-DSA sign deterministically or randomly?

ML-DSA supports both. By default, FIPS 204 recommends a “hedged” (randomized) approach where the masking vector y is generated using both a secret key seed and fresh randomness. This protects the scheme in case the system’s random number generator is compromised, while still providing the collision resilience of randomized signatures.

Why does the toy visualizer sometimes need multiple signing attempts?

That’s the rejection sampling working correctly. With these toy parameters, roughly 40-60% of masking vectors y produce a z just outside the safe bound, so the visualizer simply resamples and tries again. Real ML-DSA parameters are tuned so the expected number of attempts stays small (typically under 5).

What are “hint bits,” and why can’t the scheme work without them?

They are a small amount of extra data (at most ω bits, typically 55–80 depending on the parameter set) that let the verifier recover the exact high-order bits of w despite only having a noisy approximation of it. Without hints, the verifier’s recomputed challenge would occasionally mismatch the signer’s even for a perfectly valid signature, causing spurious rejections.

Is the visualizer’s occasional “tampered message accepted” result a bug?

No — it’s an honest artifact of the toy’s tiny challenge space. With n=4 and coefficients in {-1, 0, 1}, there are only 3⁴ = 81 possible challenge polynomials, so two different messages occasionally hash to the same challenge purely by chance. Real ML-DSA’s challenge space, drawn from hundreds of positions, is far too large for this kind of coincidence to ever occur.

How does Dilithium relate to Kyber?

They share the exact same Module-LWE key structure (t = A·s₁ + s₂ looks identical to Kyber’s t = A·s + e). The difference is entirely in what you do with the keys: Kyber uses them for encryption and key exchange, while Dilithium adds the sign-challenge-response-abort machinery on top to build a signature scheme. Together they form NIST’s matched pair of primary lattice-based standards.

References

1. NIST. “Module-Lattice-Based Digital Signature Standard.” FIPS 204, August 2024. Available at: https://csrc.nist.gov/pubs/fips/204/final

2. Ducas, L., Lepoint, T., Lyubashevsky, V., et al. “CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme.” IACR TCHES, 2018.

3. Lyubashevsky, V. “Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures.” ASIACRYPT, 2009.

4. CRYSTALS Team. “Dilithium.” Available at: https://pq-crystals.org/dilithium/