After RSA: post quantum signatures.

In 1994, Peter Shor, at Bell Labs, presented an algorithm that could not yet run on any existing machine and that nonetheless changed the horizon of all public key cryptography. He showed that a sufficiently large and stable quantum computer could factor integers and compute discrete logarithms in polynomial time. The three problems on which RSA, Diffie and Hellman, and elliptic curves rest would all fall at once.

Three decades later, that machine still does not exist, but nobody serious is betting that it never will. This final article in the series explains what exactly Shor’s algorithm breaks, what it does not, and what the signatures designed to survive it look like on the inside.

What Shor does, and what it does not

The central idea is to turn factoring into the problem of finding the period of a function. If you pick a random a, the sequence a^x mod n is periodic, and knowing its period r lets you, with high probability, obtain a factor of n by computing gcd(a^r/2 1, n). Finding that period is hard for a classical computer, but a quantum computer can prepare a superposition of all values of the function and extract the period with the quantum Fourier transform. The same principle, applied to groups, solves the discrete logarithm, including on elliptic curves.

Hash functions and symmetric ciphers fall into another category. Grover’s algorithm gives a quadratic speedup for unstructured search: finding a preimage among 2ⁿ possibilities now costs about 2^n/2 evaluations, and those evaluations are also sequential and very hard to parallelize. At 256 bits, the margin remains enormous. That is why post quantum cryptography focuses on replacing public key algorithms, not hash functions.

The oldest signature is the most modern

Paradoxically, one of the most solid post quantum families is almost as old as RSA. In 1979, Leslie Lamport described a signature built from nothing but a hash function.

1. Private key. 256 pairs of random 256 bit values: (x_i,0, x_i,1) for i from 1 to 256.
2. Public key. The hashes of all of them: (H(x_i,0), H(x_i,1)).
3. Signing. Hash the message and, for each of its 256 bits, reveal x_i,0 if the bit is 0 or x_i,1 if it is 1.
4. Verifying. Hash each revealed value and compare it with the corresponding half of the public key.

Forging requires inverting the hash function. There is no algebraic structure for Shor to exploit. But it has a severe limitation: each key is good for a single signature, because each signature reveals half of the secrets, and two signatures on different messages reveal enough to stitch together a third.

Ralph Merkle solved the problem with a tree. You generate 2^h one time keys and place their public keys as the leaves of a binary hash tree. The root, 32 bytes, is the only public key. Each signature includes the one time signature, its public key and the h sibling hashes needed to recompute the root. It is the same Merkle tree that underpins certificate transparency and evidence records.

Stateful and stateless

The modern descendants split into two branches. XMSS (RFC 8391) and LMS (RFC 8554), recommended by NIST in SP 800 208, are stateful schemes: the signer must remember which leaves it has used and never repeat one. That is a dangerous requirement in practice, because a restored backup or a cloned module can reuse a leaf without anyone noticing. That is why they are reserved for controlled uses, such as signing a device’s boot software.

SPHINCS, presented in 2015, and its successor SPHINCS+, standardized in 2024 as SLH DSA in FIPS 205, did away with state. It uses a hypertree, a tree of trees, and at the bottom level a “few time” signature scheme called FORS; the leaf is chosen pseudorandomly from the message, and the tree is so large that the probability of dangerously reusing a leaf is negligible. The price is large signatures: between about 8 and 50 kilobytes depending on the parameter set. The reward is the most conservative security assumption possible: if the hash function is good, the signature is secure.

Lattices: the needle in a noisy haystack

The other major family is based on lattices. A lattice is the set of all integer combinations of a set of basis vectors, a regular grid in a space of many dimensions. Finding the shortest nonzero vector in a lattice, given a “bad” basis, is hard in high dimensions, and no known quantum algorithm solves it efficiently.

In 2005, Oded Regev formulated the learning with errors problem, LWE, which became the foundation of practical lattice cryptography:

ML DSA, derived from the CRYSTALS Dilithium scheme and standardized in FIPS 204, uses a more efficient module version, MLWE. Its signature follows the Schnorr structure with a twist, the Fiat and Shamir with aborts method proposed by Vadim Lyubashevsky:

ML DSA comes in three levels, 44, 65 and 87, corresponding to NIST security categories 2, 3 and 5. It signs much faster than RSA and verifies at comparable speed, but its keys and signatures are measured in kilobytes. NIST also selected Falcon, another lattice scheme with more compact signatures, which is being standardized as FN DSA; implementing it securely is trickier because it requires Gaussian sampling in floating point arithmetic.

How the transition happens

No cryptographic migration has ever been fast. Moving from SHA 1 to SHA 256 in certificates took more than a decade. The post quantum transition is bigger, because it affects the signature algorithms themselves, and legally binding signatures involve secure devices, identity cards with years of service life, national roots and format standards.

• Hybrid or composite signatures. During the transition, a single document or certificate can carry both a classical and a post quantum signature, so that it remains secure as long as either one does. This protects against the quantum threat and, at the same time, against a flaw in the new algorithms, which have far less history behind them.
• Roots first. A root is distributed and trusted for decades. It is the first place where post quantum keys make sense, even if the leaves stay classical for a while.
• Archives with renewed timestamps. Existing signatures do not need to be redone. It is enough that, before classical algorithms become forgeable, an archive timestamp made with resistant algorithms covers the signature and its validation information. This is the mechanism described in this blog’s first series, applied to a new change of algorithms.
• Agility. Systems that can switch algorithms through configuration will make the transition; those with RSA hard coded will not.

The scientific method of cryptography is, at heart, a method of transitions. Diffie and Hellman replaced key distribution with public keys; elliptic curves largely replaced RSA; SHA 2 replaced SHA 1. The move to post quantum cryptography is the next step, and it will not be the last. What does not change is the pattern that ran through this entire series: a hash that captures the document, a hard problem that separates private from public, a chain that puts names to keys, and evidence that proves when each thing happened.

← All notes