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

ML-DSA Dilithium explained in full: CRYSTALS-Dilithium is the digital signature scheme standardised by NIST as ML-DSA (FIPS 204, August 2024), and it represents the most deployment-ready post-quantum signature algorithm available today. This article walks through the mathematics behind module lattices, how Dilithium generates and verifies signatures, how its key and signature sizes compare to classical schemes, and why its properties matter specifically for cryptocurrency wallets and blockchain infrastructure facing the long-term threat of quantum computers powerful enough to break ECDSA.

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

CRYSTALS-Dilithium was developed by a team of cryptographers from academia and industry, submitted to NIST's Post-Quantum Cryptography (PQC) standardisation project in 2017, and selected as a primary standard in 2022. In August 2024, NIST published it formally as FIPS 204, renaming it ML-DSA (Module Lattice-based Digital Signature Algorithm).

The "CRYSTALS" umbrella stands for Cryptographic Suite for Algebraic Lattices and covers two primitives: Kyber (now ML-KEM, a key encapsulation mechanism) and Dilithium (ML-DSA, a signature scheme). This article focuses exclusively on the signature side.

Why a New Signature Standard Was Necessary

Classical digital signature schemes, including ECDSA (used by Bitcoin and Ethereum) and RSA, derive their security from mathematical problems that a sufficiently powerful quantum computer can solve efficiently. Specifically:

• ECDSA / EdDSA rely on the Elliptic Curve Discrete Logarithm Problem (ECDLP). Shor's algorithm breaks this in polynomial time on a fault-tolerant quantum machine.
• RSA relies on integer factorisation. Shor's algorithm breaks this too.

The timeline for such machines is uncertain, but cryptographers use the term Q-day to describe the point at which these attacks become feasible. Because "harvest now, decrypt later" attacks are already occurring, migrating signature infrastructure before Q-day is a live engineering concern, not a theoretical one.

---

The Mathematics Behind Module Lattices

Understanding ML-DSA requires a working grasp of the lattice problems it relies on.

What Is a Lattice?

A lattice in the cryptographic sense is a discrete additive subgroup of n-dimensional Euclidean space, generated by a set of basis vectors. Concretely, given a matrix B, the lattice is all integer linear combinations of its rows. Security comes from the hardness of problems defined over these structures.

The Hard Problems ML-DSA Relies On

ML-DSA's security reduces to two well-studied lattice problems:

1. Module Learning With Errors (MLWE). Given samples of the form (A, As + e) where A is a public matrix, s is a small secret vector, and e is a small error vector drawn from a noise distribution, recover s. The "module" qualifier means the ring structure is parameterised, offering a middle ground between plain LWE (large keys) and ring-LWE (smaller keys but narrower security arguments).

1. Module Short Integer Solution (MSIS). Given A, find a short non-zero vector x such that Ax = 0 mod q. This underpins the unforgeability of signatures.

Both problems are believed to be hard even for quantum computers. No sub-exponential quantum algorithm is known for either, unlike ECDLP or factoring.

The Fiat-Shamir with Aborts Framework

Dilithium uses a Fiat-Shamir with Aborts construction, introduced by Lyubashevsky. The high-level flow:

1. The signer samples a random masking vector y from a bounded distribution.
2. Computes a commitment w = Ay mod q, then hashes (w, message) to produce a challenge c.
3. Computes a response z = y + cs, where s is the secret key.
4. Abort condition: if z is too large (leaks information about s), discard and restart. This rejection sampling step is critical. It ensures z reveals nothing about s regardless of how many signatures an attacker observes.
5. The signature is (z, h) where h is a hint vector helping the verifier reconstruct the high bits of w.

Verification checks that z is short, recomputes the high bits of Az - ct (where t is part of the public key), and confirms the hash matches. No secret material is exposed during verification.

---

ML-DSA Parameter Sets and Sizes

NIST standardised three parameter sets, each targeting a different NIST security level (analogous to AES-128, AES-192, and AES-256).

For comparison, common classical schemes:

The size increase is substantial. An ML-DSA-44 signature is roughly 34 times larger than an Ed25519 signature. This is the primary engineering cost of post-quantum security and has direct implications for blockchain transaction throughput, storage, and fee markets.

---

How Dilithium Compares to Other Post-Quantum Signature Schemes

NIST also standardised or is evaluating several other post-quantum signature schemes. Each makes different trade-offs.

Why Dilithium / ML-DSA Is Often the Default Choice

• Implementation simplicity. The rejection-sampling construction avoids the Gaussian sampling required by Falcon, which is notoriously difficult to implement securely in constant time without side-channel leakage.
• Conservative security assumptions. MLWE and MSIS are among the most studied lattice problems.
• No statefulness. Unlike XMSS and LMS, ML-DSA is stateless. Stateful hash-based schemes require careful key management to avoid reusing one-time signing keys, a significant operational burden.
• Broad library support. Reference and optimised implementations exist in C, Rust, Python, and Go; hardware optimisations using AVX2/AVX-512 are well-documented.

---

Implications for Cryptocurrency Wallets and Blockchain Infrastructure

This is where ML-DSA moves from academic interest to practical urgency.

The ECDSA Exposure Problem

Every Bitcoin and Ethereum address derived from an exposed public key, meaning any address that has ever signed a transaction, has its public key on-chain. A quantum adversary with Shor's algorithm can derive the private key from that public key. Addresses that have never signed a transaction (pay-to-public-key-hash where only the hash is visible) have some additional protection, but are still vulnerable once they transact.

What Post-Quantum Wallets Need From a Signature Scheme

A wallet replacing ECDSA with a post-quantum alternative needs:

1. Deterministic or stateless signing to avoid catastrophic reuse errors.
2. Reasonable signature sizes to keep transaction fees manageable.
3. Fast verification to avoid slowing down node validation.
4. Mature, audited implementations to minimise side-channel and implementation bugs.

ML-DSA satisfies all four requirements better than most alternatives. Falcon's smaller signatures are attractive, but the sampling complexity increases implementation risk, particularly on constrained hardware like hardware security modules (HSMs) and hardware wallets. SPHINCS+ is a credible fallback due to its minimal mathematical assumptions (only hash function security), but its large signatures are punishing at scale.

Hybrid Schemes During Migration

Most serious cryptographic engineering guidance, including NIST's own migration framework and ETSI guidance, recommends hybrid signatures during the transition period: a classical signature (e.g., Ed25519) and an ML-DSA signature are both computed and both verified. This ensures security against both classical and quantum adversaries simultaneously, protecting against the possibility that a new cryptanalytic result weakens ML-DSA before migration is complete.

BMIC.ai's quantum-resistant wallet implements post-quantum cryptography aligned with NIST's PQC standards, including the lattice-based primitives discussed in this article, to protect holdings against the Q-day threat.

---

Implementing ML-DSA: Practical Considerations

Key Generation

Key generation samples two small secret polynomials s1 and s2, computes t = As1 + s2, and publishes (A, t) as the public key. The matrix A is derived deterministically from a public seed, so it need not be transmitted explicitly. Key generation is fast, on the order of microseconds on modern hardware.

Signing Performance

Signing involves a rejection-sampling loop. The expected number of restarts is low (typically 1 to 4 iterations depending on the parameter set), making average-case performance acceptable. In benchmarks on a modern x86-64 processor with AVX2:

• ML-DSA-44: ~125,000 signatures/second, ~450,000 verifications/second.
• ML-DSA-65: ~80,000 signatures/second, ~300,000 verifications/second.
• ML-DSA-87: ~55,000 signatures/second, ~220,000 verifications/second.

These figures are comfortably within the performance envelope of most blockchain node and wallet applications.

Constant-Time Implementation

Lattice arithmetic involves polynomial multiplication over rings, typically accelerated by the Number Theoretic Transform (NTT), a modular analogue of the Fast Fourier Transform. NTT-based multiplication is data-independent and inherently amenable to constant-time implementation, reducing timing side-channel risk. This is a meaningful advantage over Falcon's Gaussian sampling, where constant-time guarantees are harder to achieve.

Library Ecosystem

Production-ready libraries as of 2024-2025 include:

• liboqs (Open Quantum Safe project): C, with language bindings for Python, Go, Java, .NET.
• pqcrypto crate (Rust): wraps liboqs and native Rust implementations.
• dilithium pure-Rust crate: standalone, no C dependency.
• CIRCL (Cloudflare): Go implementation, production-grade.
• BouncyCastle (Java/C#): includes FIPS 204-aligned ML-DSA.

All major implementations have received or are undergoing independent security audits. Before integrating any library into a production wallet or signing infrastructure, verify audit status and check for published CVEs.

---

The Road Ahead for ML-DSA Adoption

FIPS 204 is a final standard, not a draft. Government agencies in the US are already required to plan migration timelines. The financial sector, including digital asset custodians and exchange infrastructure, is expected to follow regulatory guidance that will increasingly mandate PQC-readiness.

For blockchain protocols, the migration path is more complex. Changing signature schemes requires consensus-layer upgrades, potential hard forks, and backward-compatibility decisions about legacy addresses. Several Layer 2 protocols and newer L1 chains are exploring ML-DSA integration at the protocol level from inception, avoiding the retrofit problem entirely.

Key open questions for the next 3 to 5 years:

• Address format changes: How to encode larger ML-DSA public keys in address standards without bloating the address space.
• Fee market adjustments: Whether fee-per-byte models need rethinking when post-quantum transactions are 10 to 30 times larger.
• Hardware wallet support: Embedding ML-DSA in constrained devices (e.g., 256 KB RAM secure elements) requires careful memory management.
• Hybrid transition standards: Standardising hybrid signature formats so that multi-vendor ecosystems interoperate cleanly.

None of these are unsolved problems in principle. They are engineering and governance challenges that the industry is actively working through.