Hash-Based Signatures

Every digital signature you have ever verified — HTTPS certificates, software updates, code-signing — ultimately rests on mathematics that a quantum computer could tear apart. RSA relies on the hardness of factoring; ECDSA relies on the hardness of the elliptic-curve discrete logarithm. Shor's algorithm, running on a large enough quantum machine, breaks both in polynomial time.

Hash-based signatures take a radically different approach: they derive their security purely from the collision resistance of a hash function. No algebraic structure. No number theory. Just the assumption that it is hard to find two inputs that hash to the same output — an assumption that Grover's algorithm weakens only quadratically, not catastrophically.

The idea traces back to Leslie Lamport in 1979. Lamport showed that a one-time signature could be built from any one-way function. Ralph Merkle then layered a hash tree on top in his 1979 PhD thesis (published 1987), allowing a single public key to authenticate thousands of messages. Today, SPHINCS+ — a stateless hash-based scheme — is one of the four algorithms selected by NIST in 2024 as a post-quantum signature standard, alongside lattice-based schemes like CRYSTALS-Dilithium.

The demo below builds a Merkle tree over four one-time key pairs. Each leaf is the hash of a one-time public key. Inner nodes are hashes of their two children. The root is the single public key published to the world.

Click Sign with leaf to sign a message using one leaf's private key. The signature includes the leaf's one-time signature plus the authentication path — the sibling hashes needed to recompute every node up to the root. Click Verify to walk that path and confirm the root matches.

<p class="hint">{{hint}}</p>
<div id="tree-vis"></div>
<div class="controls">
  <label>{{msg_label}} <input id="msg" type="text" value="{{msg_default}}" maxlength="60"></label>
  <div class="leaf-btns">
    <button id="s0" type="button">{{sign_leaf_0}}</button>
    <button id="s1" type="button">{{sign_leaf_1}}</button>
    <button id="s2" type="button">{{sign_leaf_2}}</button>
    <button id="s3" type="button">{{sign_leaf_3}}</button>
  </div>
  <button id="verify" type="button" disabled>{{verify_btn}}</button>
  <button id="reset" type="button" class="ghost">{{reset_btn}}</button>
</div>
<div id="status" class="status"></div>
<div id="sig-box" class="sig-box"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#tree-vis { margin: .5rem 0 .8rem; display: flex; flex-direction: column; align-items: center; gap: 6px; }
.tree-row { display: flex; gap: 10px; align-items: center; }
.node { display: flex; align-items: center; justify-content: center; border-radius: 6px;
        font: 600 11px ui-monospace, monospace; padding: 4px 6px; border: 1.5px solid #adb1b8;
        background: #e8eef3; color: #1d3557; white-space: nowrap; min-width: 120px; }
.node.leaf { background: #c9ccd1; border-color: #adb1b8; }
.node.leaf.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.node.root { background: #457b9d; color: #fff; border-color: #1d3557; min-width: 250px; }
.node.root.match { background: #0a7d33; border-color: #0a7d33; }
.node.root.mismatch { background: #c92f3c; border-color: #c92f3c; }
.node.auth { background: #ffc14d; border-color: #e6a820; color: #333; }
.connector { font-size: 18px; color: #aaa; user-select: none; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
.controls label { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; font-weight: 600; }
#msg { flex: 1; min-width: 180px; padding: .3rem .5rem; border: 1px solid #aaa; border-radius: 6px; font-size: .9rem; }
.leaf-btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-weight: 700; margin: .3rem 0; min-height: 1.2em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #457b9d; }
.sig-box { font: .8rem ui-monospace, monospace; background: #f0f4f8; border: 1px solid #cdd9e3;
           border-radius: 6px; padding: .5rem .7rem; white-space: pre-wrap; word-break: break-all;
           max-height: 130px; overflow-y: auto; color: #333; display: none; }

// Code not found

Notice: verification just hashes its way up the tree — fast and obvious. Forging a signature would require finding a collision in the hash function, which no known algorithm does efficiently, classically or quantum.

Hash-based signatures occupy a special place in cryptography because their security reduction is the tightest of any signing scheme:

• Security assumption: collision resistance of the underlying hash (e.g., SHA-256 or SHA3-256). If the hash is secure, the signature is secure. No other assumption is needed.
• Quantum threat: Grover's algorithm gives a quadratic speedup for finding preimages and collisions. A 256-bit hash retains roughly 128 bits of quantum security — still far beyond any foreseeable attack. Doubling the hash output (e.g., SHA3-512) restores the full classical margin.
• The state problem: Lamport and Merkle's original schemes are stateful — each one-time key must never be reused. Reusing a Lamport key leaks the private key immediately. XMSS (RFC 8391, standardized 2018) manages state carefully and is suitable for hardware security modules.
• Stateless schemes: SPHINCS+ (NIST PQC standard, 2024) eliminates state by signing a random index into a huge virtual tree. The signature is larger (~8–50 KB depending on parameters), but there is no reuse risk.
• Signature size: the main cost of hash-based schemes. SPHINCS+ signatures dwarf RSA-2048 signatures (~256 bytes) — a deliberate trade-off for the strongest possible security guarantee.

In terms of P vs NP and complexity theory, collision resistance is a one-way function assumption: we believe inverting a cryptographic hash is not in P, but we cannot prove it. The scheme's security is conditional — as with all of cryptography — but the condition is the most conservative and best-studied one available.

Hash-based signatures are the conservative choice for anything that must remain secure for decades or that handles a bounded number of signings:

• Firmware and OS updates: a device shipped today may need its update chain to stay secure in 2045. Hash-based signatures provide a credible 20-year guarantee that algebraic schemes cannot.
• Certificate authorities: the root CA key signs only a handful of intermediate certificates per year — a perfect fit for a stateful scheme like XMSS, where state management is tractable.
• Code signing for open-source software: projects like OpenSSH and GnuPG have already begun testing SPHINCS+ support.
• Blockchain anchoring: a blockchain transaction can commit a Merkle root to a public ledger, enabling compact audit trails for large sets of documents.
• Post-quantum migration: NIST's 2024 selection of SPHINCS+ alongside lattice-based schemes means governments and standards bodies worldwide are already writing migration guides. Hash-based signatures are the fallback fallback: if lattice cryptography turns out to be breakable, SPHINCS+ still stands.

The scheme's drawback — large signatures — matters less every year as bandwidth grows and storage costs fall. For high-value, low-frequency signings, hash-based schemes are today's gold standard for post-quantum security.

Hash-based signatures are a rare thing in cryptography: a scheme whose security proof requires almost nothing. Lamport showed in 1979 that a one-way function is sufficient to sign one message. Merkle showed that a hash tree turns that into a practical system. Half a century later, that lineage is a NIST standard.

The price is signature size. The reward is a guarantee untouched by quantum algorithms or unexpected breakthroughs in algebra. If every lattice problem turns out to be easy, hash-based signatures still stand — they just need collisions to be hard.

In a world racing to migrate cryptographic infrastructure before quantum computers arrive, that kind of unconditional conservatism is not timidity. It is engineering wisdom. The same lesson applies across all of post-quantum cryptography: the assumption you trust least is the one you should minimize.