Post-Quantum Cryptography and Document Authentication – ML-DSA / FIPS 204 Explained

The Quantum Computing Threat to Cryptography

Most public-key cryptography currently in use – including RSA, DSA, and elliptic curve cryptography (ECDSA) – relies on the computational difficulty of factoring large numbers or computing discrete logarithms. Classical computers cannot solve these problems in practical timeframes at the key sizes currently in use.

Quantum computers, which exploit quantum mechanical phenomena to perform certain computations, can solve these problems efficiently using Shor's algorithm. A sufficiently powerful quantum computer could break RSA-2048, ECDSA-256, and similar standards in hours rather than the billions of years required by classical computers.

Commercially viable quantum computers capable of breaking current cryptographic standards do not yet exist. However, cryptographers and security agencies assess that they will exist within one to two decades, and potentially sooner.

The “Harvest Now, Decrypt Later” Problem

Even before quantum computers capable of breaking current cryptography exist, they present a risk to long-lived data. An adversary can capture encrypted communications or signed documents today and store them for decryption or signature verification later, once the necessary quantum computing capability exists. This is known as the “harvest now, decrypt later” threat model.

For document authentication, the implications are significant. A document authenticated using classical cryptography today may have its authentication signature broken in the future. An attacker could then forge authentication signatures for fraudulent documents and claim they were authenticated at a specific historical date. The integrity of the authentication record would be compromised retroactively.

Post-Quantum Cryptography Standards

In response to the quantum computing threat, the United States National Institute of Standards and Technology (NIST) ran a multi-year competition to develop post-quantum cryptographic standards – algorithms believed to be resistant to attacks by both classical and quantum computers.

In August 2024, NIST finalised three post-quantum cryptographic standards:

—ML-KEM (FIPS 203)for key encapsulation (encryption)
—ML-DSA (FIPS 204)for digital signatures
—SLH-DSA (FIPS 205)an alternative digital signature scheme

ML-DSA (FIPS 204)

ML-DSA – Module Lattice Digital Signature Algorithm – is the primary NIST recommendation for post-quantum digital signatures. It is derived from the CRYSTALS-Dilithium submission to the NIST competition and is based on the hardness of lattice problems, specifically the Module Learning With Errors (MLWE) problem.

Lattice-based cryptography is believed to be secure against quantum attacks because the best known quantum algorithms for solving lattice problems do not provide the same exponential speedup that Shor's algorithm provides for factoring and discrete logarithm problems.

ML-DSA provides three security levels, equivalent to AES-128, AES-192, and AES-256. Audrie implements ML-DSA at the highest security level.

Why Audrie Chose ML-DSA

Audrie selected ML-DSA (FIPS 204) for document authentication signatures for three reasons.

First, it is the primary NIST recommendation for post-quantum digital signatures. NIST standards are adopted by government agencies and regulated industries globally. Implementing FIPS 204 positions Audrie's authentication records as compliant with emerging regulatory expectations for post-quantum cryptographic security.

Second, document authentication records are long-lived. A document authenticated today may need to be verified in ten or twenty years – long enough for quantum computing to advance to the point where classical cryptographic signatures are vulnerable. Post-quantum signatures protect the integrity of the authentication record for the life of the document.

Third, the cost of upgrading cryptographic implementations is high. Changing the signature algorithm after a platform is deployed requires re-authenticating all existing documents or accepting that historical records use different and weaker cryptographic standards. Implementing post-quantum cryptography from day one avoids this technical debt.

Implementation

Audrie uses ML-DSA for the cryptographic binding between an authenticator's verified identity and the document hash at the point of authentication. The signature is stored in the Audrie database alongside the document hash and the authenticator's identity reference.

Verification recomputes the document hash and checks it against the stored record, confirming that the document matches the authenticated version and that the stored record has not been tampered with.