qcve-logo

ML-DSA: A New Post-Quantum Cryptography Digital Signature Standard

Choy Shi Hong

Choy Shi Hong

Contents

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.

SetSecurity StrengthPrivate Key (B)Public Key (B)Signature (B)
ML-DSA-44Category 2256013122420
ML-DSA-65Category 3403219523309
ML-DSA-87Category 5489625924627

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.

You may also like

Be first to comment
Leave a reply