Chapter 47: Hash-Based Signatures — From Lamport to SLH-DSA#
47.1 Why Hash-Based Signatures Are Special#
Every other public-key signature scheme — RSA, DSA, ECDSA, Ed25519, ML-DSA, Falcon, multivariate, isogeny — rests on an algebraic hardness assumption: factoring, discrete logarithm, Module-LWE, MQ, isogeny walks. These assumptions are believed hard, but their hardness is not proven, and a single mathematical breakthrough could collapse them.
Hash-based signatures rest on a much weaker assumption:
The hash-based security premise
The hash function \(H \colon \{0,1\}^* \to \{0,1\}^n\) is collision-resistant (no adversary can find \(x \ne y\) with \(H(x) = H(y)\) within their resource budget) and, for some constructions, second-preimage resistant (given \(x\), no adversary can find \(y \ne x\) with \(H(x) = H(y)\)).
That is it. No number theory. No algebra. If SHA-256 (or SHA-3, or SHAKE) remains second-preimage resistant against your adversary, then your hash-based signature is secure against that adversary — period. This makes hash-based signatures the most conservatively-secure post-quantum primitive we have. They were the first PQC scheme NIST standardised (SLH-DSA, FIPS 205, 2024) precisely because the security argument is as close to bullet-proof as cryptography allows.
The price is size. SLH-DSA signatures are 8–50 KB (compare to Ed25519’s 64 bytes, or ML-DSA’s 2.5–4.6 KB). For long-term signatures on rare events (software releases, root-of-trust certificates, code-signing keys), this is acceptable. For high-volume protocols (TLS), it is generally not, and ML-DSA is preferred.
This chapter builds hash-based signatures from the ground up: from the Lamport one-time signature (1979) → Winternitz OTS (signature size trade-off) → Merkle trees (one key, many signatures) → stateful XMSS/LMS (Internet RFCs) → stateless SPHINCS+ (FIPS 205).
47.2 Lamport One-Time Signatures (1979)#
Lamport OTS
Let \(H \colon \{0,1\}^* \to \{0,1\}^n\) be a one-way hash function.
Key generation. Pick \(2n\) random secret strings \(s_{i,b} \in \{0,1\}^n\) for \(i = 0, \ldots, n-1\) and \(b \in \{0,1\}\). The secret key is the array \(\{s_{i,b}\}_{i, b}\). The public key is \(\{H(s_{i,b})\}_{i, b}\) — also \(2n\) values, each \(n\) bits.
Signing a message \(m\). Compute \(h = H(m) = h_0 h_1 \ldots h_{n-1}\). The signature is \(\sigma = (s_{0, h_0}, s_{1, h_1}, \ldots, s_{n-1, h_{n-1}})\) — one secret string per bit of the message hash.
Verification. Given \(\sigma = (\sigma_0, \ldots, \sigma_{n-1})\) and message \(m\), compute \(h = H(m)\) and check that \(H(\sigma_i) = \mathrm{pk}_{i, h_i}\) for every \(i\).
Two properties stand out:
One-time only. Each signature reveals \(n\) secret strings, one per bit of the message hash. After two signatures of different messages, the attacker knows on average \(1.5n\) of the \(2n\) secret strings: at the \(\approx n/2\) positions where the two hashes differ, both secrets are revealed; at the remaining positions only one. Each bit of a freshly chosen target hash then lands on a known secret with probability \(\approx 3/4\) — but a valid forgery requires every one of the \(n\) bits to land on a known secret, so the brute-force forger must search for a target hash whose every position is “covered” (Exercise 47.E5 in the practical sheet).
Quantum security. Both the security argument (one-wayness of \(H\)) and the Grover-quantum attack against second-preimages are well-understood. To reach 128 quantum-bits of security against Grover, take \(n \ge 256\).
For the rest of the chapter, set \(n = 256\) bits (\(= 32\) bytes) and use SHA-256.
import hashlib, os
from typing import Tuple, List
N = 32 # 256-bit security level (quantum-128)
def H(x: bytes) -> bytes:
return hashlib.sha256(x).digest()
def lamport_keygen() -> Tuple[List[List[bytes]], List[List[bytes]]]:
'''Return (sk, pk). Each is a list of 256 pairs of N-byte strings.'''
sk = [[os.urandom(N), os.urandom(N)] for _ in range(8 * N)]
pk = [[H(sk_i_b) for sk_i_b in pair] for pair in sk]
return sk, pk
def bits(x: bytes) -> List[int]:
out = []
for byte in x:
for j in range(8):
out.append((byte >> (7 - j)) & 1)
return out
def lamport_sign(sk, message: bytes) -> List[bytes]:
h = H(message)
return [sk[i][b] for i, b in enumerate(bits(h))]
def lamport_verify(pk, message: bytes, sig: List[bytes]) -> bool:
h = H(message)
for i, b in enumerate(bits(h)):
if H(sig[i]) != pk[i][b]:
return False
return True
sk, pk = lamport_keygen()
msg = b'Lamport-attacks-can-be-fixed-by-Merkle'
sig = lamport_sign(sk, msg)
print('Signature length :', len(sig), 'strings of', N, 'bytes =',
len(sig) * N, 'bytes total')
print('Verifies :', lamport_verify(pk, msg, sig))
print('Verifies (tamper):', lamport_verify(pk, msg + b'.', sig))
Signature length : 256 strings of 32 bytes = 8192 bytes total
Verifies : True
Verifies (tamper): False
47.3 Winternitz One-Time Signatures (WOTS+)#
Lamport signatures are large: \(\tfrac{n^2}{4}\) bytes of public key plus \(\tfrac{n^2}{8}\) bytes of signature for an \(n\)-bit hash. For \(n = 256\) that is 16 KB of public key and 8 KB of signature per signature.
The Winternitz construction trades signature time for size by chaining hashes. Instead of representing each bit of the message hash by one chain, we represent each \(\log_2(w)\)-bit digit by one chain.
WOTS+ at a glance
We follow the FIPS 205 convention: \(w\) is the alphabet size (typically \(w = 16\), i.e. \(\log_2 w = 4\) bits per digit). Split the \(n\)-bit message hash into
and append \(\ell_2\) checksum digits computed so that any increase of a message digit forces a decrease of a checksum digit.
For each of the \(\ell = \ell_1 + \ell_2\) digit positions, derive a chain \(x \to H(x) \to H(H(x)) \to \cdots\) of length \(w - 1\). The secret key is the \(\ell\) chain starts; the public key is the \(\ell\) chain ends.
To sign digit \(d_i\), publish \(H^{d_i}(\mathrm{sk}_i)\) — the chain truncated \(d_i\) steps in. To verify, the verifier hashes the published value \(w - 1 - d_i\) further times and checks against \(\mathrm{pk}_i\).
The checksum prevents an attacker from forging by increasing one digit (which would cost only further hashing) without triggering a decrease elsewhere — and decreases require inverting the chain, which is preimage-resistant.
For \(n = 256\) bits and \(w = 16\) we get \(\ell_1 = 64\) and \(\ell_2 = 3\), hence \(\ell = 67\). With per-chain output of \(32\) bytes, the WOTS+ signature is \(\ell \cdot 32 = 2144\) bytes ≈ 2.1 KB (vs Lamport’s 8 KB). The verifier performs up to \(\ell \cdot (w - 1) = 67 \cdot 15 = 1005\) hash evaluations.
Why WOTS+, not WOTS?
The “+” in WOTS+ refers to a 2011 improvement by Hülsing that replaces the naive iterated-hash chain with a masked iteration \(H_{r_i}(x) := H(x \xor r_i)\) using public per-step bitmasks \(r_i\). This eliminates a multi-target attack on plain WOTS and brings the security back to \(n\) bits classically (and \(n/2\) quantum-bits via Grover).
# A toy WOTS implementation (without the "+" bitmasks; production code uses
# masks per Hülsing 2013). This is enough to see the size/time trade-off.
import math, struct
W = 16 # Winternitz parameter
WBITS = W.bit_length() - 1 # bits per digit (4 for w=16)
LEN1 = (8 * N + WBITS - 1) // WBITS # digits in message hash -> 64
LEN2 = (math.floor(math.log2(LEN1 * (W - 1))) // WBITS) + 1 # checksum digits
LEN = LEN1 + LEN2
def H_chain(x: bytes, steps: int) -> bytes:
for _ in range(steps):
x = H(x)
return x
def to_digits(msg_hash: bytes):
out = []
bit_buf, bits_in_buf = 0, 0
for byte in msg_hash:
bit_buf = (bit_buf << 8) | byte
bits_in_buf += 8
while bits_in_buf >= WBITS:
bits_in_buf -= WBITS
out.append((bit_buf >> bits_in_buf) & (W - 1))
return out
def base_w(msg: bytes):
digits = to_digits(H(msg))[:LEN1]
csum = sum(W - 1 - d for d in digits)
csum_bytes = csum.to_bytes((LEN2 * WBITS + 7) // 8, 'big')
digits += to_digits(csum_bytes)[:LEN2]
return digits
def wots_keygen():
sk = [os.urandom(N) for _ in range(LEN)]
pk = [H_chain(s, W - 1) for s in sk]
return sk, pk
def wots_sign(sk, msg):
return [H_chain(sk[i], d) for i, d in enumerate(base_w(msg))]
def wots_verify(pk, msg, sig):
return all(H_chain(sig[i], W - 1 - d) == pk[i]
for i, d in enumerate(base_w(msg)))
sk_w, pk_w = wots_keygen()
msg_w = b'WOTS-can-sign-once'
sig_w = wots_sign(sk_w, msg_w)
print(f'WOTS parameters : w={W} (so {WBITS} bits/digit), '
f'len = {LEN1} + {LEN2} = {LEN} chains')
print(f'WOTS signature size: {LEN * N} bytes '
f'(Lamport had {2 * 8 * N * N // 8} bytes for same hash size)')
print(f'WOTS verifies : {wots_verify(pk_w, msg_w, sig_w)}')
print(f'WOTS verifies tamp.: {wots_verify(pk_w, msg_w + b"x", sig_w)}')
WOTS parameters : w=16 (so 4 bits/digit), len = 64 + 3 = 67 chains
WOTS signature size: 2144 bytes (Lamport had 2048 bytes for same hash size)
WOTS verifies : True
WOTS verifies tamp.: False
47.4 Merkle Trees: One Public Key, Many Signatures#
The Merkle one-time-signature schemes above bind one Lamport (or WOTS+) key pair to one signature. To sign \(2^h\) messages with one published public key, Ralph Merkle (1979) introduced what we now call the Merkle tree.
Generate \(2^h\) independent OTS key pairs \((\mathrm{sk}^{(j)}, \mathrm{pk}^{(j)})\) for \(j = 0, \ldots, 2^h - 1\). Compute leaf hashes \(\ell_j = H(\mathrm{pk}^{(j)})\) and build a binary tree by hashing pairs:
The public key is just the root \(r\) of the tree — one hash, \(n\) bytes. A signature on the \(j\)-th message consists of:
the OTS signature \(\sigma^{(j)}\) produced from \(\mathrm{sk}^{(j)}\);
the OTS public key \(\mathrm{pk}^{(j)}\);
the authentication path — the \(h\) sibling hashes along the path from leaf \(j\) to the root.
To verify, recompute the leaf hash \(H(\mathrm{pk}^{(j)})\), walk up the tree combining with the authentication path, and check that the result equals the public root.
Why this works
The security of Merkle’s construction reduces to (i) the OTS being unforgeable, and (ii) the hash function being collision-resistant. No new assumptions, no new mathematics. It is the most boring and the most robust signature scheme on the planet.
def merkle_build(leaf_pks: List[List[List[bytes]]]) -> List[List[bytes]]:
'''Build a binary Merkle tree from leaf OTS public keys. Return all levels.'''
leaves = [H(b''.join(b''.join(pair) for pair in pk)) for pk in leaf_pks]
levels = [leaves]
cur = leaves
while len(cur) > 1:
nxt = []
for i in range(0, len(cur), 2):
nxt.append(H(cur[i] + cur[i + 1]))
levels.append(nxt)
cur = nxt
return levels # levels[0] = leaves; levels[-1] = [root]
def merkle_auth_path(levels: List[List[bytes]], j: int) -> List[bytes]:
path = []
for lvl in levels[:-1]:
sibling_idx = j ^ 1 # flip last bit -> sibling
path.append(lvl[sibling_idx])
j //= 2
return path
def merkle_verify(root: bytes, leaf_pk_hash: bytes, j: int,
path: List[bytes]) -> bool:
cur = leaf_pk_hash
for sib in path:
if j % 2 == 0:
cur = H(cur + sib)
else:
cur = H(sib + cur)
j //= 2
return cur == root
# Build a height-3 Merkle MSS over 2^3 = 8 Lamport keys.
H_HEIGHT = 3
N_LEAVES = 1 << H_HEIGHT
all_sk, all_pk = [], []
for _ in range(N_LEAVES):
sk_j, pk_j = lamport_keygen()
all_sk.append(sk_j)
all_pk.append(pk_j)
levels = merkle_build(all_pk)
public_root = levels[-1][0]
print('Public root (32 bytes):', public_root.hex())
# Sign message #5 in the tree.
J = 5
msg = b'Five fish in five seas.'
ots_sig = lamport_sign(all_sk[J], msg)
auth_path = merkle_auth_path(levels, J)
print('Sig consists of: 1 OTS sig + 1 OTS pk + h auth-path nodes;',
' total bytes =', len(ots_sig) * N + sum(len(b''.join(p)) for p in all_pk[J])
+ len(auth_path) * N)
leaf_hash = H(b''.join(b''.join(pair) for pair in all_pk[J]))
ok_ots = lamport_verify(all_pk[J], msg, ots_sig)
ok_path = merkle_verify(public_root, leaf_hash, J, auth_path)
print('OTS verifies:', ok_ots, ' Path verifies:', ok_path)
# How does signature size scale with tree height? Each Merkle MSS signature
# carries (one OTS sig + one OTS pk + h auth-path nodes). The OTS payload
# dominates; the auth path adds 32*h bytes for SHA-256. Measure on Lamport
# (worst case) to make the trend visible.
import time as _time
print()
print(' h | leaves | keygen(s) | sig bytes | of which auth-path bytes')
print('---+--------+-----------+-----------+-------------------------')
for h_test in (2, 4, 6):
n_leaves = 1 << h_test
t0 = _time.time()
sks_t, pks_t = zip(*(lamport_keygen() for _ in range(n_leaves)))
levels_t = merkle_build(list(pks_t))
keygen_t = _time.time() - t0
auth_path_bytes = h_test * N
ots_sig_bytes = 8 * N * N # 256 secret strings * 32 bytes
ots_pk_bytes = 2 * 8 * N * N
sig_bytes = ots_sig_bytes + ots_pk_bytes + auth_path_bytes
print(f' {h_test} | {n_leaves:6d} | {keygen_t:8.2f} | {sig_bytes:9d} | {auth_path_bytes:5d}')
print()
print('The auth-path overhead (32*h bytes) is negligible compared with the OTS')
print("payload — so once you fix the OTS, taller trees buy you many more")
print('signatures essentially for free. This is why WOTS+ replaces Lamport in')
print('XMSS / LMS / SPHINCS+: cutting OTS bytes by ~4x makes huge trees viable.')
Public root (32 bytes): 5c8c75ab2d33dab586b5964eba03d01076292d8f07d4a3e484150afd02e76274
Sig consists of: 1 OTS sig + 1 OTS pk + h auth-path nodes; total bytes = 24672
OTS verifies: True Path verifies: True
h | leaves | keygen(s) | sig bytes | of which auth-path bytes
---+--------+-----------+-----------+-------------------------
2 | 4 | 0.00 | 24640 | 64
4 | 16 | 0.01 | 24704 | 128
6 | 64 | 0.04 | 24768 | 192
The auth-path overhead (32*h bytes) is negligible compared with the OTS
payload — so once you fix the OTS, taller trees buy you many more
signatures essentially for free. This is why WOTS+ replaces Lamport in
XMSS / LMS / SPHINCS+: cutting OTS bytes by ~4x makes huge trees viable.
47.5 XMSS and LMS — Stateful Hash-Based Standards#
The Merkle MSS above has one painful flaw: the signer must remember which leaves they have already used. Reusing a Lamport leaf reveals its secrets; reusing a WOTS+ leaf permits trivial forgery via the standard Winternitz multi-signature attack. This is the state requirement.
In the 2010s, two stateful hash-based signature schemes were standardised:
XMSS — eXtended Merkle Signature Scheme. Buchmann, Dahmen, Hülsing (2011). Standardised in RFC 8391 (May 2018). Uses WOTS+ leaves, masked Merkle hashing.
LMS — Leighton–Micali Signatures. Standardised in RFC 8554 (April 2019). Uses LM-OTS (a Winternitz variant) and HSS hyper-trees for scaling.
NIST recommends both in SP 800-208 (2020) for specific narrow use cases where the signer can guarantee that no leaf is ever signed twice. Typical example: signing firmware releases from an HSM in a tightly-controlled deployment pipeline.
Why state is dangerous in practice
Imagine a signer hosted in a VM. The hypervisor takes a snapshot, then later restores the VM from the snapshot. Without a hardware monotonic counter, the restored signer happily re-uses leaves it already used in the original timeline — and silently breaks the signature scheme. This is not a hypothetical: it is the reason NIST issued SP 800-208 with explicit, narrow deployment guidance, and the reason SPHINCS+ exists.
47.6 SPHINCS+ / SLH-DSA — Going Stateless#
SPHINCS+ is a hash-based signature scheme that eliminates the state requirement at a modest cost in signature size. It is now standardised as SLH-DSA in FIPS 205 (August 2024). The scheme is by Bernstein, Hülsing, Kölbl, Niederhagen, Rijneveld, and Schwabe (CCS 2019).
The key idea is a hyper-tree of fixed height \(h\) together with few-time signatures (FORS) at the leaves, plus a deterministic but pseudorandom leaf selector driven by the message itself. Concretely:
Build a Merkle hyper-tree of total height \(h\) (FIPS 205 uses \(h \in \{63, 64, 66, 68\}\) across its six parameter sets). Each layer of the hyper-tree has its own subtree height \(h' = h / d\).
At each subtree node, use a WOTS+ key pair to sign the root of the subtree below.
At the leaves of the hyper-tree, place FORS (Forest Of Random Subsets) few-time signatures — these can sign a small number of messages without catastrophic key reuse.
To sign a message, derive a leaf index pseudorandomly from the message. Sign the message hash with that leaf’s FORS instance, then publish the chain of WOTS+ subtree-root signatures up to the public root.
Because the leaf index is derived from the message, two distinct messages almost certainly hit different FORS leaves, so the few-time-signature property never fires. Even if (by birthday luck) two messages collide on the same FORS leaf, FORS is designed to remain secure for several messages per leaf.
Parameter sets you should know
FIPS 205 names the parameter sets SLH-DSA-{SHA2,SHAKE}-128/192/256{f,s},
where the trailing f is “fast” (larger signatures) and s is “small”
(slower). Levels 128/192/256 match NIST security categories 1/3/5,
i.e. ML-KEM-512/768/1024. Sample sizes:
Parameter set |
Public key |
Signature |
|---|---|---|
SLH-DSA-SHA2-128f (fast) |
32 B |
17 088 B (~16.7 KB) |
SLH-DSA-SHA2-128s (small) |
32 B |
7 856 B (~7.7 KB) |
SLH-DSA-SHA2-256s |
64 B |
29 792 B (~29 KB) |
For the highest level, signatures push 50 KB. ML-DSA, by contrast, is 2.5–4.6 KB.
47.7 The State-Reuse Catastrophe — Demonstrated#
If the signer of an XMSS / LMS instance accidentally signs two distinct messages with the same WOTS+ leaf, the consequences are catastrophic. Let us build the cleanest possible demonstration: a Lamport leaf signed twice on distinct messages.
# For demonstration only, we use a truncated 16-bit hash so the forgery search
# completes in seconds. With a real 256-bit hash, the attacker still acquires the
# same fraction of secrets, but locating a third message whose hash lands only on
# already-known positions becomes a hash-preimage problem (chosen-prefix
# collisions or NIST hash-inversion records). The vulnerability is identical
# in shape; only the brute-force budget changes.
DEMO_HASH_BITS = 16
def H_demo(x: bytes) -> bytes:
return hashlib.sha256(x).digest()[: DEMO_HASH_BITS // 8]
def lamport_keygen_demo():
sk = [[os.urandom(N), os.urandom(N)] for _ in range(DEMO_HASH_BITS)]
pk = [[H(s) for s in pair] for pair in sk]
return sk, pk
def bits_demo(x: bytes):
out = []
for byte in x:
for j in range(8):
out.append((byte >> (7 - j)) & 1)
return out
def lamport_sign_demo(sk, message):
return [sk[i][b] for i, b in enumerate(bits_demo(H_demo(message)))]
def lamport_verify_demo(pk, message, sig):
return all(H(sig[i]) == pk[i][b]
for i, b in enumerate(bits_demo(H_demo(message))))
sk_leaf, pk_leaf = lamport_keygen_demo()
msg1 = b'Send 100 PLN to Alice.'
msg2 = b'Send 999 PLN to Bob.'
sig1 = lamport_sign_demo(sk_leaf, msg1)
sig2 = lamport_sign_demo(sk_leaf, msg2)
assert lamport_verify_demo(pk_leaf, msg1, sig1)
assert lamport_verify_demo(pk_leaf, msg2, sig2)
# Attacker observes both (msg, sig) pairs. The two signatures together reveal
# sk[i][h1[i]] AND sk[i][h2[i]] at every position i. At positions where
# h1[i] != h2[i] the attacker now knows BOTH secrets at that position.
h1 = bits_demo(H_demo(msg1))
h2 = bits_demo(H_demo(msg2))
known = {}
for i, (b1, b2) in enumerate(zip(h1, h2)):
known[(i, b1)] = sig1[i]
known[(i, b2)] = sig2[i]
print(f'Hash size for demo : {DEMO_HASH_BITS} bits')
print(f'Differing positions : {sum(a != b for a, b in zip(h1, h2))}/{DEMO_HASH_BITS}')
print(f'Secrets known : {len(known)}/{2 * DEMO_HASH_BITS}')
def forge(msg, known):
h = bits_demo(H_demo(msg))
out = []
for i, b in enumerate(h):
if (i, b) not in known:
return None
out.append(known[(i, b)])
return out
# Brute force a third message whose hash lands entirely on known positions.
for trial in range(200_000):
msg3 = f'Send 1000 PLN to Mallory. salt={trial}'.encode()
forged = forge(msg3, known)
if forged is not None:
print(f'Forged signature for {msg3.decode()!r} after {trial:,} tries')
print('Forged sig verifies:', lamport_verify_demo(pk_leaf, msg3, forged))
break
else:
print('No forgeable message found — try again or grow the budget.')
Hash size for demo : 16 bits
Differing positions : 10/16
Secrets known : 26/32
Forged signature for 'Send 1000 PLN to Mallory. salt=132' after 132 tries
Forged sig verifies: True
When you run the cell above, the attacker should land a forgery within a few thousand random trials (the success probability per trial is roughly \((3/4)^{16} \approx 1\%\) — when half of the hash positions differ between the two signed messages, the attacker has both secrets at those positions and one secret at the rest).
Scale the same logic to the real 256-bit hash and the per-trial probability falls to \((3/4)^{256} \approx 2^{-106}\). So in production the attacker cannot brute-force random third messages — they need to invert the hash function onto a chosen target set of bit positions, which is the hash-preimage problem. Whether or not that is feasible depends on the hash function and the target, but the point stands: two signatures from the same Lamport leaf irrevocably weaken the scheme, and the consequences range from “near-total compromise” (weak hash) to “tractable preimage attack” (real hash). SPHINCS+/SLH-DSA exists specifically to remove this failure mode.
47.8 Exercises#
Exercise 47.1 — WOTS+ from scratch.
Implement WOTS+ for \(n = 32\), \(w = 16\). Verify that key generation, signing, and verification work for a 256-bit message hash. Measure the actual signature size in bytes and compare with the prediction \(\ell \cdot n\) where \(\ell = \ell_1 + \ell_2\) is computed from \(w\).
Exercise 47.2 — Merkle tree timing.
Build Merkle trees of height \(h = 4, 8, 12, 16\) over WOTS+ leaves. For each, measure (a) the keygen time, (b) the per-signature time, (c) the verifier time, and (d) the public-key and signature byte-counts. Plot \(h\) vs each metric on a log–log axis.
Exercise 47.3 — FORS sketch.
A FORS instance for \(k\)-out-of-\(2^t\) leaves works as follows: split the message hash into \(k\) chunks of \(t\) bits; for each chunk \(i\), publish the leaf at index \(\mathrm{chunk}_i\) in the \(i\)-th of \(k\) Merkle trees of height \(t\), together with its authentication path. Implement FORS for \(k = 14\), \(t = 12\) and verify that two distinct messages hash to almost-never the same leaf set.
Exercise 47.4 — Reproduce the catastrophe at scale.
Modify the demonstration in §47.7 so that the attacker, given \(r\) signatures under one leaf, computes the expected fraction of forgeable messages (closed form). Plot this fraction as a function of \(r\) for \(r = 2, 3, \ldots, 8\).
Exercise 47.5 (project candidate) — SLH-DSA reference.
Pick the SLH-DSA-SHA2-128s parameter set. Read FIPS 205 Algorithm 17 (slh_sign)
and Algorithm 18 (slh_verify). Using only hashlib and the WOTS+, FORS, and
Merkle tree primitives you built in earlier exercises, implement the full
SLH-DSA signing and verification. Verify on a sample message. Compare the
signature size you obtain with the FIPS 205 specification (7 856 bytes).
47.9 Summary#
Hash-based signatures are the most conservatively-secure post-quantum signature primitive — their security reduces to one-wayness and collision-resistance of a hash function, no algebra required.
Lamport (1979) is the simplest one-time signature: 2 secret strings per message-hash bit, signing reveals one of each pair.
Winternitz / WOTS+ trades signing time for signature size by chaining hashes; reduces signature size by ~4× at \(w = 16\).
Merkle trees (1979) bind \(2^h\) OTS keys to a single \(n\)-byte public root, at the cost of authentication-path overhead.
XMSS (RFC 8391) and LMS (RFC 8554) standardise stateful hash-based signatures for narrow deployments where state can be guaranteed.
SPHINCS+ / SLH-DSA (FIPS 205) eliminates state via FORS leaves and a pseudorandom leaf selector, at the cost of 8–50 KB signatures.
The state-reuse catastrophe demonstrates why statelessness matters in practice, and why FIPS 205 was the first NIST PQC signature standard to publish.
47.10 References#
Lamport, L. (1979). Constructing Digital Signatures from a One-Way Function. SRI Technical Report CSL-98.
Merkle, R. C. (1979). Secrecy, Authentication and Public Key Systems. Stanford PhD thesis.
Hülsing, A. (2013). W-OTS+ — Shorter Signatures for Hash-Based Signature Schemes. AFRICACRYPT 2013.
Buchmann, J., Dahmen, E., Hülsing, A. (2011). XMSS — A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions. PQCrypto 2011.
IETF RFC 8391 (May 2018). XMSS: eXtended Merkle Signature Scheme.
IETF RFC 8554 (April 2019). Leighton–Micali Hash-Based Signatures.
NIST SP 800-208 (October 2020). Recommendation for Stateful Hash-Based Signature Schemes.
Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., Schwabe, P. (2019). The SPHINCS⁺ Signature Framework. CCS ‘19.
NIST FIPS 205 (August 2024). Stateless Hash-Based Digital Signature Standard. https://csrc.nist.gov/pubs/fips/205/final
Aumasson, J.-P., Bernstein, D. J., et al. (2020). SPHINCS+ submission package, round 3. https://sphincs.org