ML-DSA Dilithium Explained: How Lattice-Based Signatures Work

ML-DSA Dilithium explained — this article breaks down one of the most important cryptographic standards to emerge from NIST's post-quantum standardisation process. You will learn how CRYSTALS-Dilithium constructs digital signatures from hard lattice problems, why its security assumptions resist quantum attack, how signature and key sizes compare to classical schemes like ECDSA, and what adoption looks like in the real world, including cryptocurrency wallets built around post-quantum security. No hand-waving: this is a technically grounded explainer suitable for developers, security researchers, and informed crypto holders.

What Is ML-DSA and Where Did It Come From?

ML-DSA stands for Module-Lattice-Based Digital Signature Algorithm. It is the formal NIST designation published in FIPS 204 (August 2024) for what the cryptographic community had previously called CRYSTALS-Dilithium. The two names refer to the same algorithm: Dilithium was the submission name used throughout NIST's Post-Quantum Cryptography (PQC) standardisation project, which ran from 2016 to 2024. Once NIST finalised the standard, it renamed the scheme ML-DSA to align with its broader naming convention for lattice-based primitives.

The algorithm was designed by a team of researchers from CWI Amsterdam, Ruhr-Universität Bochum, ENS Lyon, and other institutions. It was selected alongside ML-KEM (formerly Kyber, a key-encapsulation mechanism) as the primary NIST-approved post-quantum primitive intended for general-purpose digital signatures.

Why a New Signature Standard Was Needed

Every digital signature scheme in widespread use today — ECDSA (used in Bitcoin and Ethereum), EdDSA (Ed25519), and RSA-PSS — relies on mathematical problems that a sufficiently powerful quantum computer can solve efficiently:

• ECDSA / EdDSA security rests on the Elliptic Curve Discrete Logarithm Problem (ECDLP). Shor's algorithm solves ECDLP in polynomial time on a quantum computer.
• RSA security rests on integer factorisation. Shor's algorithm breaks that too.

This vulnerability is not theoretical speculation. The academic and intelligence communities refer to "Q-day" as the point at which fault-tolerant quantum hardware becomes capable of running Shor's algorithm against real-world key sizes. Harvest-now-decrypt-later attacks are already a documented threat model: adversaries can record encrypted traffic or signed data today and decrypt or forge signatures once quantum capability matures.

ML-DSA was standardised precisely to give software engineers and protocol designers a drop-in signature scheme that does not depend on these broken assumptions.

---

The Mathematical Foundation: Module Lattices

To understand ML-DSA, you need a working model of what a lattice is and why the hard problems defined over lattices are believed to resist quantum attack.

What Is a Lattice?

A lattice is a regular grid of points in high-dimensional space, generated by taking all integer linear combinations of a set of basis vectors. Formally, given basis vectors b₁, b₂, …, bₙ, the lattice L is:

```

L = { a₁b₁ + a₂b₂ + … + aₙbₙ : aᵢ ∈ ℤ }

```

The basis can be expressed in many equivalent ways. Some bases make the lattice structure obvious; others (called "bad" or "reduced" bases) make it computationally very hard to solve geometric problems on the lattice.

Hard Lattice Problems

Two related problems underpin ML-DSA's security:

• Learning With Errors (LWE): Given many noisy linear equations over a lattice, find the hidden secret vector. Even with unlimited quantum computation, no polynomial-time algorithm for LWE is known.
• Short Integer Solution (SIS): Given a random matrix A, find a short non-zero vector z such that Az = 0 mod q. This is hard to solve even quantumly.

ML-DSA operates over module lattices, meaning it works with matrices of polynomials over a ring (specifically, polynomials modulo a cyclotomic polynomial). This Module-LWE / Module-SIS setting lets the scheme tune security levels efficiently by changing the module dimension k × l rather than redesigning the entire primitive.

Why Quantum Computers Cannot Break This

Shor's algorithm exploits the algebraic structure of cyclic groups. Lattice problems do not have the same exploitable structure. The best known quantum algorithms for LWE and SIS (based on quantum variants of lattice sieving) provide only modest speedups over classical algorithms, and those speedups are accounted for in the parameter choices. There is no known sub-exponential quantum algorithm for Module-LWE.

---

How ML-DSA Constructs a Digital Signature

ML-DSA follows the Fiat-Shamir with Aborts paradigm, pioneered by Lyubashevsky. Here is the construction at a conceptual level:

Key Generation

1. Sample a random matrix A (public, derived from a seed).
2. Sample secret vectors s₁ and s₂ with small coefficients (drawn from a bounded distribution).
3. Compute t = As₁ + s₂.
4. The public key is (A, t). The private key is (s₁, s₂) (plus a commitment for efficiency).

The security of the public key rests on Module-LWE: an adversary seeing t cannot recover s₁ or s₂.

Signing

1. Sample a random masking vector y with bounded coefficients.
2. Compute a commitment w = Ay.
3. Generate a challenge c by hashing the message together with a compressed version of w.
4. Compute the response z = y + cs₁.
5. Abort and restart if z or certain intermediate values exceed a coefficient bound. This abort step is critical: it prevents leaking information about the secret s₁ through the response vector.
6. Output the signature (z, c, h) where h is a hint vector used to allow the verifier to reconstruct the high bits of w from the public key alone.

Verification

1. Reconstruct w' from Az - ct using the hint h.
2. Re-derive the challenge c' by hashing the message against the reconstructed w'.
3. Accept if c' = c and the coefficient norms of z are within bounds.

The abort mechanism means signing is probabilistic in runtime — on average, the signer restarts approximately 4 to 7 times per signature across the standard parameter sets, but each attempt is fast.

---

Parameter Sets and Security Levels

FIPS 204 defines three parameter sets for ML-DSA, mapped to NIST security categories:

For comparison, an ECDSA signature over secp256k1 (the Bitcoin curve) is 64 bytes, and the compressed public key is 33 bytes. ML-DSA signatures are roughly 35 to 70 times larger.

What Those Size Differences Mean in Practice

Larger signatures have real-world consequences:

• Blockchain storage: A Bitcoin block could fit fewer transactions if every signature were ML-DSA-sized. Protocol designers must plan for this, either through batching, aggregation research, or off-chain signing.
• TLS handshakes: A single TLS 1.3 handshake using ML-DSA-65 adds roughly 3 KB over the wire. For high-volume APIs, this is measurable but manageable.
• Wallet UX: For a user signing a single transaction, the overhead is invisible. The wallet handles it internally.
• Signing speed: ML-DSA is fast. On a modern x86-64 processor with AVX2 instructions, ML-DSA-65 signs in under 0.1 ms and verifies in under 0.15 ms. Key generation is similarly quick.

The performance story is therefore good. The bandwidth story requires protocol adaptation, particularly for high-frequency blockchain use cases.

---

ML-DSA vs. Other Post-Quantum Signature Schemes

NIST standardised one additional signature algorithm alongside ML-DSA and is evaluating more:

ML-DSA is the practical default for most new deployments. It has the broadest hardware support, the clearest implementation guidance, and the most mature tooling. Falcon's smaller signatures are attractive for constrained environments, but its Gaussian sampling requires careful constant-time implementation to avoid side-channel leakage. SLH-DSA is the most conservative choice (it requires no lattice hardness assumption), but its large signatures and slower signing make it a secondary option.

---

Implementation and Adoption Status

Open-Source Libraries

Mature, audited implementations of ML-DSA exist in:

• liboqs (Open Quantum Safe project): C library with language bindings for Python, Java, Go, Rust, and .NET.
• pqcrypto crates (Rust): Idiomatic Rust bindings for FIPS 204 parameter sets.
• BouncyCastle (Java/C#): Dilithium/ML-DSA included since version 1.73.
• OpenSSL 3.x with OQS provider: Allows ML-DSA in TLS 1.3 connections via provider plug-in.
• AWS-LC and Google's BoringSSL forks have experimental or production ML-DSA support for internal services.

Adoption in Standards and Protocols

• IETF has active drafts for ML-DSA in TLS 1.3, X.509 certificates, and SSH.
• Apple announced post-quantum iMessage upgrades using ML-KEM; signature upgrades are in roadmap.
• Signal Protocol introduced PQXDh using ML-KEM for forward secrecy. Signature layer upgrades follow a separate timeline.
• CNSA 2.0 (NSA's Commercial National Security Algorithm Suite 2.0) mandates ML-DSA for software signing by 2030 in US national security systems.

Adoption in Cryptocurrency Infrastructure

Cryptocurrency wallets represent one of the most sensitive deployment environments for signature schemes, because a compromised signing key means irreversible loss of funds. Quantum exposure is a long-horizon but structurally serious risk: the public key of any address that has ever spent funds is exposed on-chain permanently.

Projects building post-quantum-resistant wallet infrastructure are beginning to adopt ML-DSA or hybrid classical-plus-ML-DSA schemes for key derivation and transaction signing. BMIC.ai is one such project, applying NIST PQC-aligned lattice-based cryptography to protect wallet keys against the eventual Q-day threat. Hybrid approaches, where both ECDSA and ML-DSA signatures must validate, are considered prudent during the transition period because they do not reduce security even if lattice assumptions are later weakened.

---

Security Considerations and Known Limitations

ML-DSA is not a silver bullet. Implementers should be aware of:

• Side-channel attacks: The abort-and-restart mechanism can leak timing information if not implemented in constant time. Reference implementations include guidance on avoiding this.
• No signature aggregation: Unlike BLS signatures (used in Ethereum consensus), ML-DSA signatures cannot be naively aggregated. Research into lattice-based aggregation is ongoing but not yet standardised.
• Statelessness is a feature: Unlike older hash-based schemes (XMSS, LMS), ML-DSA is stateless. Signers do not need to track a counter. This eliminates an entire class of implementation bugs related to state synchronisation.
• Random number quality: The masking vector y must be sampled from a high-quality RNG. A weak or reused nonce does not immediately break ML-DSA the way it breaks ECDSA (where nonce reuse directly reveals the private key), but poor randomness degrades security margins.
• Parameter set choice: Use ML-DSA-65 or ML-DSA-87 for applications with long-lived keys or high-value assets. ML-DSA-44 is appropriate where the security lifetime is short and bandwidth is constrained.

---

Summary: Key Takeaways

• ML-DSA (CRYSTALS-Dilithium) is the NIST FIPS 204 standard for post-quantum digital signatures, based on the hardness of Module-LWE and Module-SIS.
• It uses the Fiat-Shamir with Aborts paradigm: key generation, a masking-based signing loop, and efficient verification via hint vectors.
• Three parameter sets cover NIST security levels 2, 3, and 5, with signature sizes ranging from ~2.4 KB to ~4.6 KB.
• Signatures are 35 to 70 times larger than ECDSA, but signing and verification are extremely fast on modern hardware.
• It is the primary recommended post-quantum signature algorithm for new protocol deployments, with growing adoption across TLS, software signing, and cryptocurrency infrastructure.
• Quantum computers cannot efficiently solve Module-LWE or Module-SIS with any known algorithm, making ML-DSA the current gold standard for long-term signature security.