01 — Why We Need ML-DSA

What Digital Signatures Do

A digital signature is a cryptographic proof that binds three things:

1. A message — the document, software, or transaction
2. A signer — identified by their public key
3. A moment in time — the signature cannot be created before the private key existed

Unlike a handwritten signature (easy to forge), a digital signature is:

• Unforgeable — only the private key holder can create it
• Verifiable — anyone with the public key can check it
• Non-repudiable — the signer cannot later deny having signed

Where Signatures Are Used

The Quantum Threat

How Shor's Algorithm Forges Signatures

RSA signatures:

• Signature: σ = m^d mod n (where d is the private key)
• Verification: σ^e ≡ m mod n (where e is the public key)
• Shor's algorithm factors n, recovering d from (n, e)
• Result: Anyone can now forge signatures

ECDSA/EdDSA signatures:

• Signature: (r, s) where s = k⁻¹(H(m) + d·r)
• d is the private key (discrete log of public key Q = d·G)
• Shor's algorithm solves the discrete log, recovering d
• Result: Anyone can now forge signatures

Timeline

The "Harvest Now, Forge Later" Attack

Even more insidious than decrypting recorded traffic:

1. Adversary records signed documents/transactions today.
2. They don't need to break anything now.
3. In 10–15 years, they use a quantum computer to recover private keys from public keys.
4. They forge backdated signatures on fraudulent documents.
5. Legal, financial, and audit systems collapse because signature validity can no longer be trusted.

This is why we must transition BEFORE quantum computers exist.

What ML-DSA Fixes

ML-DSA signatures are based on the Short Integer Solution (SIS) problem over lattices:

Given a matrix A and a bound β, find a short vector s such that A·s = 0 (mod q) and ||s|| ≤ β.

This problem has no periodic structure for Shor's algorithm to exploit. The best known quantum attack (Grover's) provides only a square-root speedup — insufficient to break practical parameters.

What Doesn't Change

Only the signature algorithm changes. The surrounding infrastructure (hashing, certificate formats, trust chains) stays the same.

Resources

• Shor, "Algorithms for quantum computation" (1994)
• NIST IR 8547: Transition to Post-Quantum Cryptography
• CA/Browser Forum: Baseline Requirements updates for PQC certificates