Nearly every digital signature in use today — RSA, ECDSA, Ed25519 — rests on a number-theory problem that a large quantum computer would solve efficiently. Hash-based signatures take a radically narrower bet: they assume only that a secure hash function exists. That single assumption makes them the most conservative quantum-resistant signatures we have, and the story of how they're built is one of the most elegant in cryptography.

A digital signature scheme rests on some hard problem. RSA rests on the difficulty of factoring large numbers; elliptic-curve schemes rest on the discrete logarithm problem. Shor's algorithm, run on a sufficiently large quantum computer, breaks both. That is the entire motivation for post-quantum cryptography: replacing those foundations with problems quantum computers are not known to solve quickly.

Most post-quantum signature proposals lean on relatively young assumptions — structured lattices, in the case of the lattice schemes now being standardized. Hash-based signatures lean on something far older and far better understood: the security of cryptographic hash functions. We have studied hash functions for decades, we use them everywhere, and a secure hash is the minimal assumption you could possibly want. If your hash function holds, your signatures hold. That is the entire pitch, and it is a strong one.

Lamport: A Signature From Nothing But Hashing

The foundation is the Lamport one-time signature, described by Leslie Lamport in 1979. The idea is almost shockingly simple. To sign a single bit, you generate two random secret values and publish their hashes as your public key. To sign a "0," you reveal the first secret; to sign a "1," you reveal the second. Anyone can hash the revealed value and check it against the public key, but no one can produce the other secret, because a hash function cannot be run backwards.

Extend that to a full message by hashing the message to a fixed-length digest and signing each of its bits with its own pair of secrets. The security rests entirely on the one-way property of the hash. There is no modular arithmetic, no elliptic curve, no factoring — just hashing.

Why "one-time" is in the name: Each Lamport key pair can safely sign exactly one message. Signing a second message reveals more of your secret values, and an attacker who collects enough revealed secrets across multiple signatures can begin forging. The "use once" rule is not a suggestion — it is load-bearing.

Winternitz: Trading Time for Space

Lamport signatures are simple but large, because you need secret pairs for every bit. The Winternitz one-time signature scheme (WOTS, and the refined WOTS+) shrinks them by signing several bits at once using repeated hashing — applying the hash function a number of times that encodes the value, rather than revealing one of two secrets per bit. The result is a tunable trade-off: more hashing per signature in exchange for smaller keys and signatures. WOTS+ is the one-time building block inside the practical schemes that follow.

Merkle Trees: One Public Key for Many Signatures

A one-time signature you can only use once is not much of a signature scheme. Ralph Merkle's insight, also from the late 1970s, turns it into a usable one. Generate many one-time key pairs. Hash all their public keys into the leaves of a binary Merkle tree, and let the single root of that tree be your one real public key.

Now you can sign many messages: each signature uses a fresh one-time key from a leaf, and includes the "authentication path" — the sequence of sibling hashes that lets a verifier climb from that leaf back to the published root. The verifier confirms the one-time signature, then confirms the leaf belongs to the tree whose root they trust. One compact public key now authenticates thousands or millions of one-time keys.

The State Problem

This construction — the Merkle signature scheme and its modern descendants XMSS (RFC 8391) and LMS (RFC 8554) — is efficient and well understood. NIST approved XMSS and LMS in Special Publication 800-208. But it carries a sharp and dangerous requirement: it is stateful. The signer must remember which leaves have already been used and never reuse one.

That sounds trivial until you think about real systems. Restore a virtual machine from a snapshot, and you roll the state back to a point where unused leaves now appear unused again — and you sign with a leaf you already burned. Clone a server, run two copies, and they share a counter. Any of these reuses a one-time key, and one-time keys are catastrophic to reuse. The cryptography is sound; the operational discipline is brutal.

A stateful hash-based scheme is only as safe as your guarantee that you will never, under any backup, migration, or failure, sign twice with the same leaf. For many deployments that guarantee is simply not achievable.

SPHINCS+: Paying to Be Stateless

The answer to the state problem is SPHINCS+, which NIST selected and standardized as SLH-DSA in FIPS 205 in 2024. SPHINCS+ is stateless: it eliminates the dangerous counter entirely. Instead of tracking which leaf to use, it selects one pseudorandomly from such an enormous space that accidental collisions are negligible, and it layers a hypertree of Merkle trees together with a few-time signature scheme (FORS) to make that work securely.

The price is size and speed. SPHINCS+ signatures are large — on the order of several kilobytes to tens of kilobytes depending on the parameter set, far bigger than a 64-byte Ed25519 signature — and signing is comparatively slow. What you buy with that cost is the removal of state management and a security argument resting on nothing but the strength of the underlying hash function. For a signing key that must remain trustworthy for decades, many designers consider that the most defensible trade available.

When to Reach for Them

Hash-based signatures are not the default choice for high-volume, latency-sensitive work — the lattice-based ML-DSA (Dilithium) is faster and more compact for general use. Where hash-based schemes shine is anywhere you want the most conservative possible security foundation and can tolerate larger signatures: firmware and software signing, long-lived roots of trust, and any key whose compromise decades from now would be unacceptable. Their value is precisely that they do not depend on a young, structured assumption that might fall to future cryptanalysis.

This is cryptographic agility reasoning in practice: matching the conservatism of the primitive to the lifetime of the thing it protects. A session key that lives for minutes can take a more aggressive bet; a code-signing root that must hold for twenty years should take the most boring, best-understood assumption available.

The Deeper Point

Hash-based signatures are a reminder that cryptographic strength is, fundamentally, about the quality of your assumptions. The entire edifice — one-time signatures, Winternitz compression, Merkle authentication, hypertrees — is built to extract a full, practical signature scheme from the single premise that a hash function is hard to invert. There is a quiet rigor to that. It refuses to assume anything it doesn't have to.

That same instinct guides how Haven approaches the cryptography underneath encrypted messaging: prefer well-understood, widely-vetted primitives over novel constructions, and keep verification tests green so the foundations stay sound as the field moves toward a post-quantum world. The most trustworthy systems are usually the ones that assume the least.

Originally published at havenmessenger.com