ML-DSA: A New Post-Quantum Cryptography Digital Signature Standard
We take a look at the new FIPS 204 post-quantum digital signature scheme, and highlight some key differences in usage between ML-DSA and classical digital signature algorithms.
The U.S.' National Institute of Standards and Technology (NIST) published three new standards in August 2024 portending a major revolution in the field of cryptography - start of post-quantum migration.
The three publications are:
FIPS 203, 204, and 205 describe new post-quantum cryptography standards, which details new cryptographic algorithms that are resistant against quantum computers.
How did we get here?
Cryptographers have long been warning the world that the rise of quantum computers will be a threat to the confidentiality and authenticity of practically all communications on the internet. Peter Shor developed Shor's Algorithm in 1994, demonstrating an efficient algorithm to solve the discrete logarithm problem with a quantum computer, and most of the internet communication relies on cryptographic algorithms RSA and ECC, which are based precisely on the discrete logarithm problem. We also previously explained breaking RSA in this article.
NIST announced a call for proposal in December 2016 for submissions of quantum-resistant algorithms. Finally, in August 2024, selected algorithms have been published as standards.
A New Digital Signature
In this post, we will focus on the new post-quantum digital signature algorithm.
Here is the abstract of FIPS 204:
Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. This standard specifies ML-DSA, a set of algorithms that can be used to generate and verify digital signatures. ML-DSA is believed to be secure, even against adversaries in possession of a large-scale quantum computer. - National Institute of Standards and Technology
In summary, FIPS 204 details a new post-quantum digital signature scheme, where the algorithm is called Module-Lattice-Based Digital Signature Algorithm (ML-DSA).
ML-DSA has three parameter sets, corresponding to three different security strengths. The size (in bytes) of the keys and signatures are also included in the table below.
| Set | Security Strength | Private Key (B) | Public Key (B) | Signature (B) |
|---|---|---|---|---|
| ML-DSA-44 | Category 2 | 2560 | 1312 | 2420 |
| ML-DSA-65 | Category 3 | 4032 | 1952 | 3309 |
| ML-DSA-87 | Category 5 | 4896 | 2592 | 4627 |
The security strength categories roughly correspond to the security definitions of block ciphers and hash functions:
- Level 2 - collision search on a 256-bit hash function (e.g., SHA-256/ SHA3-256)
- Level 3 - key search on a block cipher with a 192-bit key (e.g., AES-192)
- Level 5 - key search on a block cipher with a 256-bit key (e.g., AES-256)
Similar to the classical digital signature algorithms, ML-DSA has a "hedged" variant and a "deterministic" variant.
Differences with classical DSAs
ML-DSA has some key differences in usage compared to the classical Digital Signature Algorithms like RSA and ECDSA.
Context String
The Sign and Verify functions accept a new parameter called context string. By default, the context string is an empty string, but applications may specify a context string up to 255 bytes.
ML-DSA.Sign
flowchart LR
sk{{Private Key}} --> Sign
m{{Message}} --> Sign
ctx{{Context String}} --> Sign
Sign --> sig{{Signature}}
ML-DSA.Verify
flowchart LR
pk{{Public Key}} --> Verify
m{{Message}} --> Verify
sig{{Signature}} --> Verify
ctx{{Context String}} --> Verify
Verify --> res{{Valid/Invalid}}
As with classical DSAs, one can sign the digest of the message as opposed to the message directly. This version is called "pre-hash" ML-DSA, or HashML-DSA, and has a different identifier (e.g. OID) than ML-DSA.
The identifier also indicates the hash function or XOF (extendable-output function) used to compute the digest and must be an approved hash function or XOF. In fact, the OID is included as part of the computation of the signature.
HashML-DSA.Sign
flowchart LR
sk{{Private Key}} --> Sign
d{{Digest}} --> Sign
hash{{Pre-hash Fn}} --> Sign
ctx{{Context String}} --> Sign
Sign --> sig{{Signature}}
HashML-DSA.Verify
flowchart LR
pk{{Public Key}} --> Verify
d{{Digest}} --> Verify
hash{{Pre-hash Fn}} --> Verify
sig{{Signature}} --> Verify
ctx{{Context String}} --> Verify
Verify --> res{{Valid/Invalid}}
Conclusion
In this post, we summarised the new FIPS 204 post-quantum digital signature scheme, and highlighted some key differences in usage between ML-DSA and classical digital signature algorithms.
As the threat of quantum computers gets nearer, the internet infrastructure must be ready to transit to post-quantum cryptography as soon as possible.
Author
Choy Shi Hong
Shi Hong is a Cryptographic Engineer at pQCee.com. With formal education in Mathematics, he is curious and fascinated by the world of mathematics and technology, and feels right at home in the \(\cap\) of these two fields: cryptography.