CRYSTALS-Dilithium (ML-DSA)

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
• Python Implementation
• Limitations
• 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). It also rejects 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, forming 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 it runs 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.

Python Implementation

This mirrors the visualizer’s own toy parameters described above (n=4, q=8192): the real Module-LWE key structure, the real reject-and-resample abort loop, and a genuine Decompose/MakeHint/UseHint mechanism for recovering the verifier’s noisy approximation of w:

import random
import hashlib

n, q = 4, 8192
k, l = 2, 2
eta = 2          # secret coefficient bound
gamma1 = 512      # masking range: y coefficients in [-(gamma1-1), gamma1]
beta = 16         # safety margin subtracted from gamma1 for the bound check
alpha = 1024      # Decompose's bucket width; q/alpha = 8 buckets

def poly_mul(a, b):
    result = [0] * n
    for i in range(n):
        for j in range(n):
            idx, sign = (i + j, 1) if i + j < n else (i + j - n, -1)
            result[idx] = (result[idx] + sign * a[i] * b[j]) % q
    return result

def poly_add(a, b):
    return [(x + y) % q for x, y in zip(a, b)]

def poly_sub(a, b):
    return [(x - y) % q for x, y in zip(a, b)]

def small_poly(bound):
    return [random.randint(-bound, bound) for _ in range(n)]

def small_vec(size, bound):
    return [small_poly(bound) for _ in range(size)]

def mat_vec_mul(A, v):
    result = [[0] * n for _ in range(len(A))]
    for i in range(len(A)):
        for j in range(len(v)):
            result[i] = poly_add(result[i], poly_mul(A[i][j], v[j]))
    return result

def vec_add(a, b):
    return [poly_add(x, y) for x, y in zip(a, b)]

def vec_sub(a, b):
    return [poly_sub(x, y) for x, y in zip(a, b)]

def max_abs_centered(poly):
    return max(min(c % q, q - c % q) for c in poly)

def decompose(r):
    """Splits r into (r1, r0) with r = r1*alpha + r0 and r0 in (-alpha/2, alpha/2]."""
    r = r % q
    r0 = r % alpha
    if r0 > alpha // 2:
        r0 -= alpha
    r1 = (r - r0) // alpha
    r1 %= (q // alpha)  # wrap the top bucket back to 0
    return r1, r0

def high_bits_vec(v):
    return [[decompose(c)[0] for c in poly] for poly in v]

def make_hint(w1, w1_approx):
    """The exact per-coefficient correction the verifier needs to recover w1 from its approximation."""
    buckets = q // alpha
    return [[(a - b) % buckets for a, b in zip(pw1, paw1)] for pw1, paw1 in zip(w1, w1_approx)]

def use_hint(hint, w1_approx):
    buckets = q // alpha
    return [[(a + h) % buckets for a, h in zip(paw1, ph)] for paw1, ph in zip(w1_approx, hint)]

def hash_to_challenge(message, w1):
    flat = b''.join(c.to_bytes(2, 'big') for poly in w1 for c in poly)
    digest = hashlib.sha256(message + flat).digest()
    return [(digest[i] % 3) - 1 for i in range(n)]  # ternary: n=4 coefficients in {-1,0,1}

def keygen():
    A = [[[random.randrange(q) for _ in range(n)] for _ in range(l)] for _ in range(k)]
    s1 = small_vec(l, eta)
    s2 = small_vec(k, eta)
    t = vec_add(mat_vec_mul(A, s1), s2)
    return (A, t), (s1, s2)

def sign(message, A, t, s1, s2):
    attempts = 0
    while True:
        attempts += 1
        y = small_vec(l, gamma1)
        w = mat_vec_mul(A, y)
        w1 = high_bits_vec(w)
        c = hash_to_challenge(message, w1)
        z = vec_add(y, [poly_mul(c, s1_i) for s1_i in s1])
        if max(max_abs_centered(p) for p in z) >= gamma1 - beta:
            continue  # the abort: this candidate would leak information about s1

        r = vec_sub(mat_vec_mul(A, z), [poly_mul(c, t_i) for t_i in t])  # r = A*z - c*t = w - c*s2
        w1_approx = high_bits_vec(r)
        hint = make_hint(w1, w1_approx)
        return (z, c, hint), attempts

def verify(message, signature, A, t):
    z, c, hint = signature
    if max(max_abs_centered(p) for p in z) >= gamma1 - beta:
        return False
    r = vec_sub(mat_vec_mul(A, z), [poly_mul(c, t_i) for t_i in t])
    w1_recovered = use_hint(hint, high_bits_vec(r))
    return hash_to_challenge(message, w1_recovered) == c

if __name__ == "__main__":
    (A, t), (s1, s2) = keygen()
    message = b"HELLO"

    signature, attempts = sign(message, A, t, s1, s2)
    print(f"Signed after {attempts} attempt(s)")
    print(f"Verifies (correct message):  {verify(message, signature, A, t)}")
    print(f"Verifies (tampered message): {verify(b'HELLO!', signature, A, t)}")

Every run generates a fresh key pair and fresh masking vectors, so there’s no single fixed signature to reproduce. I ran 300 independent trials instead, all of which produced a valid signature (matching the article’s description of the typical 1-3 attempts) that verified correctly, with tampered messages rejected except for the rare accidental collision the FAQ below already explains.

Limitations

This mirrors the visualizer’s toy parameters exactly, not real ML-DSA’s production-scale ones:

• n=4, q=8192 instead of n=256, q=8380417. At this scale the underlying lattice problem is trivially solvable; the code demonstrates the reject-and-resample mechanism, not anything resembling real security.
• A simplified, more generous hint encoding. Real ML-DSA restricts each hint bit to a single ±1 nudge, chosen for bandwidth efficiency in the standardized encoding. This code’s make_hint instead stores the exact bucket-index correction needed, which is simpler to implement correctly at toy scale but wouldn’t compress as tightly as the real scheme’s format.
• No secondary bound checks. The Signing (with Aborts) section above mentions that real ML-DSA also rejects based on the low-order bits of r and a limit on the total number of hint bits (ω); this code only implements the primary bound check on z.
• Uses Python’s random, not a CSPRNG. Real lattice cryptography needs cryptographically secure, carefully-distributed randomness throughout; random.randint here is for demonstration only.
• Never use this, or hand-rolled lattice cryptography of any kind, in production. Real applications should use a vetted library’s ML-DSA implementation.

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₂. It’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 so, 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/