Dilithium (ML-DSA)

Dilithium, now officially named ML-DSA (Module Lattice Digital Signature Algorithm), is the primary post-quantum digital signature scheme standardized by NIST as FIPS 204 in August 2024. While Kyber (ML-KEM) handles key encapsulation, Dilithium handles digital signatures, the cryptographic primitive used to authenticate messages, sign certificates, and verify software integrity. Together they form the core of the NIST post-quantum cryptography suite.

Signatures vs key encapsulation

A key encapsulation mechanism (like Kyber) lets two parties establish a shared secret key. A digital signature scheme (like Dilithium) lets one party sign a message so that anyone with the public key can verify the signature’s authenticity. These are fundamentally different cryptographic operations:

• KEM: Alice and Bob agree on a shared secret (used for encrypting communications)
• Signatures: Alice signs a document; Bob verifies the signature came from Alice

Both RSA signatures and ECDSA signatures are vulnerable to Shor’s algorithm, making a post-quantum replacement essential for the entire public key infrastructure (PKI) including TLS certificates, code signing, and document signatures.

The Fiat-Shamir with aborts construction

Dilithium uses the “Fiat-Shamir with aborts” framework, a technique for building signature schemes from lattice problems:

1. Commitment: The signer generates a random masking vector $\mathbf{y}$ and computes $\mathbf{w} = \mathbf{A}\mathbf{y}$, where $\mathbf{A}$ is the public matrix.

2. Challenge: A hash function applied to $\mathbf{w}$ and the message produces a challenge $c$ with small coefficients.

3. Response: The signer computes $\mathbf{z} = \mathbf{y} + c\mathbf{s}$, where $\mathbf{s}$ is the secret key.

4. Rejection sampling (the “abort”): If $\mathbf{z}$ would reveal information about the secret key $\mathbf{s}$ (because its distribution depends on $\mathbf{s}$), the signer discards this attempt and starts over. This rejection step is critical: without it, an attacker could statistically recover $\mathbf{s}$ from many signatures.

The rejection sampling means that signing requires multiple attempts on average (typically 4 to 7), but each attempt is fast, so the overall signing time remains practical.

Parameter sets and sizes

Parameter set	Security level	Public key	Signature	Secret key
ML-DSA-44	NIST Level 2 (~AES-128)	1,312 bytes	2,420 bytes	2,560 bytes
ML-DSA-65	NIST Level 3 (~AES-192)	1,952 bytes	3,293 bytes	4,032 bytes
ML-DSA-87	NIST Level 5 (~AES-256)	2,592 bytes	4,595 bytes	4,896 bytes

Compared to ECDSA (64-byte signatures, 32-byte public keys), Dilithium signatures are significantly larger. Compared to RSA-2048 (256-byte signatures), they are also larger. However, Dilithium’s signing and verification speeds are competitive with or faster than RSA, and the sizes are manageable for most applications.

Comparison with ECDSA and RSA

Property	ECDSA (P-256)	RSA-2048	ML-DSA-65
Public key size	64 bytes	256 bytes	1,952 bytes
Signature size	64 bytes	256 bytes	3,293 bytes
Sign speed	Fast	Slow	Fast
Verify speed	Moderate	Fast	Very fast
Quantum resistant	No	No	Yes

The main trade-off is size. For applications like TLS certificates or blockchain transactions where signature size matters, Dilithium’s larger signatures increase bandwidth. For applications where speed matters most, Dilithium performs well.

Why it matters for learners

Digital signatures underpin trust on the internet. Every TLS certificate, every software update, every signed email relies on signature schemes. The transition from ECDSA and RSA to Dilithium is one of the largest cryptographic migrations in history, driven directly by the threat of quantum computers. Understanding Dilithium connects the theoretical power of quantum algorithms to the practical infrastructure changes happening across the technology industry. The “harvest now, decrypt later” threat is less acute for signatures than for encryption (you cannot forge a signature retroactively), but certificate authorities and long-lived signing keys still need migration.

See also

• Lattice-Based Cryptography
• NIST PQC Standards
• Kyber (ML-KEM)
• SPHINCS+ (SLH-DSA)