ML-DSA

Overview

ML-DSA (formerly Dilithium) is a lattice-based digital signature scheme standardized in FIPS 204. It is the primary NIST-recommended post-quantum digital signature algorithm for general-purpose use, suitable for document signing, code signing, TLS authentication, and certificate issuance.

Security basis

Security relies jointly on the hardness of Module-LWE and Module-SIS (Short Integer Solution) over polynomial rings. Both problems benefit from decades of study in the lattice cryptography literature. The scheme follows the Fiat-Shamir with Aborts paradigm, where signing may require multiple attempts before producing a valid signature that does not leak information about the secret key. No known classical or quantum algorithm threatens the selected parameters.

Key characteristics

• Hedged signing — FIPS 204 supports both deterministic and randomized signing modes. Randomized signing (hedged mode) mixes additional randomness to provide resilience against certain fault and side-channel attacks.
• Rejection sampling — the signing algorithm uses rejection sampling (abort and retry) to ensure signatures are statistically independent of the secret key, which is essential for security but means signing time has some variance.
• Moderate sizes — public keys range from 1,312 to 2,592 bytes and signatures from 2,420 to 4,627 bytes, larger than classical ECDSA but manageable for most protocols.
• Fast verification — verification is dominated by a single NTT and matrix-vector multiplication, making it substantially faster than signing.

Considerations

Correct constant-time implementation of the rejection sampling loop is critical. Implementations that leak timing information about the number of signing attempts can compromise the secret key. The secret key in FIPS 204 includes the public key, adding 32 bytes beyond what the pre-standard Dilithium specification used. Batch verification is possible and yields meaningful speedups when verifying many signatures under the same or different public keys.