Can you sign with nothing but a hash function, and what does it cost?
What Shor's algorithm takes and what it leaves, the two families of replacement (lattices and hashes) and what they weigh, and the order in which a real system moves. This is the section the tools on the post-quantum page put into practice.
Every signature scheme so far in this course leaned on a hard algebraic problem, factoring or a discrete logarithm, and that is exactly what Shor's algorithm attacks. There is a way to sign that leans on nothing but a hash function. Leslie Lamport described it in 1979: for each bit of the message digest you publish the hashes of two secrets, and to sign you reveal the one secret that matches the bit. Anyone can hash what you revealed and check it against what you published. A forger would have to produce a secret for the opposite bit, which means inverting the hash.
The catch is in the name. The key is good for one signature, because each signature uses up half the secrets. To sign many messages you build a tree: Ralph Merkle's idea of hashing the public keys together pair by pair, up to a single root that becomes the one public key. To sign with key number k you include a short path of hashes that proves key k hangs under the root.
The strength of this approach is that its security is as old and as well studied as the hash function itself. Against a quantum computer, a hash loses only the square-root factor of topic 02, which a large enough digest absorbs. NIST chose this family as the conservative backup to the lattice signature, in FIPS 205.
Lamport signatures. For an n-bit digest, the private key is 2n random secrets xi0, xi1 and the public key is their hashes H(xib). To sign a digest with bits b1…bn, reveal xibi for each i. A verifier recomputes each hash and compares. For n = 8 the key has 16 secrets and a signature reveals 8 of them; signing a second message whose digest differs in some positions reveals the other secret at those positions, and from then on a forger can mix the revealed values to sign messages whose digests agree with what has been exposed. The toy confirms that a signature verifies for the message it signs and fails for another message.
Merkle trees. A tree of height h holds 2h one-time keys under one root. For h = 2 (four keys) a proof for key 2 is the two hashes H(key 3) and H(key 0, key 1) and the verifier recomputes the root in two steps. For h = 10 the tree holds 1,024 one-time keys, so one 32-byte public key can stand for 1,024 signatures, each carrying a path of 10 hashes.
What it costs. The signature carries the revealed secrets and the path, so it is large. In the SLH-DSA-SHA2-128s parameter set of FIPS 205 the public key is 32 bytes and a signature is 7,856 bytes, about 123 times the 64 bytes of an ECDSA P-256 signature. It is also slow to produce. The designs trade size and speed for the smallest possible assumption.
Sign one message with a fresh Lamport key, then a second with the same key, and watch which of the 16 secrets have been revealed. Then forge a third message: the page searches for one whose digest is covered by what you have already exposed, and the verifier accepts it. A real key would have 512 secrets and the search would be hopeless in one use, trivial with enough reuse.
Firmware and software signing Stateful hash-based schemes, LMS (RFC 8554) and XMSS (RFC 8391), are specified for exactly the case that cannot wait: a device signed once at the factory that must still verify its updates in twenty years. The “stateful” part is a real hazard, since reusing a one-time key breaks the scheme, which is why the stateless SLH-DSA (SPHINCS+) exists.
The honest comparison Hash-based signatures are the right answer when you want the weakest assumption and can live with kilobytes. Lattice signatures (ML-DSA, 3,309 bytes at level 65) are smaller and faster and rest on a newer assumption. Standards now offer both, and a careful migration plan uses the choice on purpose.
Check yourself
A Lamport one-time signature reveals one secret from each pair. Why must the key be used only once?
Signing reveals one secret per position. A second message with a different digest reveals the other secret at the positions where the digests differ, and a forger can then assemble signatures for other messages from the revealed values.