Chapter 14: One-time signatures from hash functions

Part II built encryption and key exchange from lattices; Part III builds signatures from hash functions alone. A Lamport one-time signature lets a signer reveal selected preimages of a published list of hashes, and a verifier checks that each revealed value hashes back to the right slot. The scheme uses nothing beyond a cryptographic hash function.

Its security has two layers. On a fixed-length digest, Lamport is one-time unforgeable when the function that publishes the secret values is one-way (preimage-resistant): a forger must invert a hash on a position it never saw revealed. Because this chapter signs a message by first hashing it to a digest $d = H(m)$, the message-digest function must also resist finding a different message with the same digest as a signed one. Otherwise the same Lamport signature on the digest verifies for both messages. The phrase “one-time” stays load-bearing: the claim holds for exactly one signed digest. The target security game is EUF-CMA from Chapter 6: an adversary with access to a signing oracle must forge on a new message.

Notation: throughout this chapter, $n$ denotes the hash output length in bits (matching the Lamport digest width in the per-page examples). Chapters 15 through 18 switch $n$ to bytes for the scheme descriptions, matching the FIPS 205 and SPHINCS+ convention, and state the unit explicitly where their hash-cost discussions return to bits. Appendix B carries the scope-collision table. Part II used $n$ for lattice dimension. Each use is local.

The catch is in “one-time.” After two signatures under the same key, an adversary who sees both can mix the revealed preimages and reduce forgery to a constrained digest search. After enough reuse, the key collapses completely. The Merkle tree construction fixes this by placing many one-time public keys as leaves of a binary hash tree and publishing only the root. Each signature carries one Lamport signature plus a short authentication path from the leaf to the root. The signer tracks which leaves have been used; the verifier checks the path and the Lamport signature in sequence.

A Lamport signature at eight bits

Lamport’s construction needs one ingredient: a function $H$ that is easy to compute forward and hard to invert (Lamport, 1979). SHA-256 is a concrete standard hash function we use for the toy construction in this chapter. The scheme works at any output length $n$. This section walks it at $n = 8$ so the full key fits on a page.

Key generation. Sample $n = 8$ pairs of random 32-byte strings. Each pair $(s_0^{(i)}, s_1^{(i)})$ is one secret-key slot. Hash each string to get the public-key slot: $p_0^{(i)} = H(s_0^{(i)})$ and $p_1^{(i)} = H(s_1^{(i)})$. The secret key is the list of 8 pairs; the public key is the list of 8 hash pairs.

Signing. Hash the message to an $n$-bit digest $d = H(m)$. For each bit position $i$, reveal the secret that corresponds to $d_i$: if $d_i = 0$, reveal $s_0^{(i)}$; if $d_i = 1$, reveal $s_1^{(i)}$. The signature is the list of $n$ revealed secrets.

Verification. Hash each revealed secret and check that it matches the public-key slot indexed by the same digest bit. If all $n$ checks pass, accept.

The snippet below runs the full cycle at $n = 8$ on the single-byte message 0xA3:

import hashlib

seed = b"ch14-toy"
n = 8

# Key generation: 8 secret pairs and their SHA-256 public-key hashes.
sk = []
pk = []
for i in range(n):
    s0 = hashlib.sha256(seed + (2 * i).to_bytes(4, "big")).digest()
    s1 = hashlib.sha256(seed + (2 * i + 1).to_bytes(4, "big")).digest()
    sk.append((s0, s1))
    pk.append((hashlib.sha256(s0).digest(), hashlib.sha256(s1).digest()))

# Sign the single-byte message 0xA3.
message = bytes([0xA3])
digest = hashlib.sha256(message).digest()

# Extract the first 8 bits of the digest (MSB-first within the byte).
bits = [(digest[0] >> (7 - i)) & 1 for i in range(8)]
print(bits)
# ==> [0, 1, 1, 0, 1, 1, 0, 1]

# The signature reveals one secret per digest bit.
sig = [sk[i][bits[i]] for i in range(n)]

# Verification: hash each revealed secret and compare.
ok = all(
    hashlib.sha256(sig[i]).digest() == pk[i][bits[i]]
    for i in range(n)
)
print(ok)
# ==> True

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch14/, one file per block. Appendix C covers the clone and the environment they run on.

The digest of 0xA3 under SHA-256 starts with the byte 0x6d, which is 01101101 in binary. The signature reveals $s_0^{(0)}$ (bit 0 is 0), $s_1^{(1)}$ (bit 1 is 1), $s_1^{(2)}$ (bit 2 is 1), and so on. After signing, the signer has published exactly one preimage per bit position. The remaining 8 preimages stay secret. The eight-bit digest is a structural illustration only: a second message with the same eight-bit digest turns up in about $2^8$ tries, so an eight-bit instance is forgeable for arbitrary messages even after one signature. The next section sets the digest width that makes that search infeasible. The secrets here are derived deterministically from a seed with SHA-256 so the transcript reproduces. Production key generation draws each secret from a CSPRNG, or from a pseudorandom function over a seed with per-position domain separation, as FIPS 205 does (National Institute of Standards and Technology, 2024).

Preimage resistance, collision resistance, and Grover’s query cost

Chapter 3 defined three security properties of a cryptographic hash function $H: \{0,1\}^* \to \{0,1\}^n$ (Boneh & Shoup, 2023).

Preimage resistance: given $y$, find $x$ with $H(x) = y$. Cost: $O(2^n)$.

Second-preimage resistance: given $x$, find $x' \neq x$ with $H(x') = H(x)$. Cost: $O(2^n)$.

Collision resistance: find any pair with $H(x) = H(x')$. Cost: $O(2^{n/2})$ (birthday bound).

Chapter 6 defined the EUF-CMA game: an adversary with access to a signing oracle must produce a valid signature on a message it never queried (Goldwasser et al., 1988). Lamport OTS achieves one-time EUF-CMA (OT-EUF-CMA): the adversary gets exactly one signing query. The Merkle tree construction below lifts this to $2^d$ queries.

Grover’s algorithm searches an unstructured space of $N$ elements for a marked item using $O(\sqrt{N})$ quantum oracle queries (Grover, 1996). Applied to preimage search: a classical adversary inverts an $n$-bit hash in $O(2^n)$ evaluations; a quantum adversary using Grover search inverts it in $O(2^{n/2})$ evaluations. The query-model consequence: $n = 256$ gives $2^{128}$ ideal serial quantum hash queries for a preimage, and $n = 192$ gives $2^{96}$.

NIST’s post-quantum security categories compare an attack’s resources against those needed to break a reference primitive, not a fixed number of bits. Categories 1, 3, and 5 are keyed to exhaustive key search on AES-128, AES-192, and AES-256; categories 2 and 4 to collision search on SHA-256 and SHA-384 (National Institute of Standards and Technology, 2016). The comparison spans several resource metrics, and NIST bounds the usable quantum circuit depth (MAXDEPTH) rather than counting abstract oracle calls. Jaques et al. give the depth-limited and unconstrained AES Grover circuit costs that comparison draws on (Jaques et al., 2020).

The query-model rule of thumb is the useful summary: Grover turns an $n$-bit preimage search into about $2^{n/2}$ evaluations, so for hash-based signatures the quantum preimage cost of $2^{n/2}$ hash evaluations gives a binding parameter floor. SLH-DSA places this cost at the AES-128, AES-192, and AES-256 levels for categories 1, 3, and 5. In this chapter’s bit notation those are 128-, 192-, and 256-bit hash outputs. FIPS 205 measures the same parameter $n$ in bytes, so its parameter sets use $n = 16$, $n = 24$, and $n = 32$ (National Institute of Standards and Technology, 2024).

Collision and second-preimage resistance enter twice. At the message hash, an adversary who finds any two messages with the same digest can have one signed and reuse that signature on the other. XMSS and SLH-DSA close that route by prepending a per-signature randomizer before hashing; the textbook construction here omits it. SP 800-208 §9.2 explains the randomized hashing LMS and XMSS use (Chapter 15) (Cooper et al., 2020), and FIPS 205 §4.1 specifies SLH-DSA’s own message randomizer (Chapter 17) (National Institute of Standards and Technology, 2024). At the Merkle tree level, an adversary who collides two internal-node inputs, or finds a second preimage of a leaf, can try to substitute a rogue subtree. The classical generic collision cost is $O(2^{n/2})$ (birthday bound).

Why the quantum collision bound is not a category number

The Brassard-Hoyer-Tapp algorithm finds collisions in about $O(2^{n/3})$ quantum queries in the black-box model, but that query bound assumes about $2^{n/3}$ classically computed table entries held in quantum-accessible memory for coherent lookup, and it does not translate into NIST category bits (Brassard et al., 1998). NIST compares attacks across several resource metrics. Its reference table expresses the SHA-3 collision costs as classical gate counts, while AES key search carries depth-limited quantum-gate estimates (National Institute of Standards and Technology, 2016).

Hash-based signatures are designed not to lean on plain collision resistance. RFC 8391 states that XMSS “is even secure when the collision resistance of the underlying hash function is broken” (Hülsing et al., 2018). The SPHINCS+ proof framework behind SLH-DSA uses tweakable-hash notions and multi-target mitigations rather than plain collision resistance (Aumasson et al., 2020). FIPS 205 specifies the resulting algorithm and describes its security as resting on preimage resistance and related hash-function properties (National Institute of Standards and Technology, 2024). Chapter 17 walks how addressed, tweakable hashing achieves that.

The same authentication-path pattern shows up directly in blockchain block headers. Bitcoin commits the transaction Merkle root to every block header, and a light client verifies a transaction by walking an authentication path from the leaf to the committed root. Stateful hash-based schemes such as XMSS reuse the structure on the signer side: publish a Merkle root as the long-lived public key, then authenticate each one-time signature against the root via an authentication path (Merkle, 1989). Part VII develops the L1 signature migration that uses this authentication-path structure.

Building the Lamport and Merkle constructions

Lamport OTS at 256 bits

The $n = 8$ example above scales to $n = 256$ with no structural change. The secret key is 256 pairs of 32-byte strings (16,384 bytes). The public key is 256 pairs of SHA-256 digests (16,384 bytes). A signature is 256 revealed secrets (8,192 bytes). These sizes are large by any standard. The tradeoffs section below compares them against the compressed schemes in Chapters 15 and 16.

import hashlib

seed = b"ch14-full"
n = 256

# Key generation at n = 256.
sk = []
pk = []
for i in range(n):
    s0 = hashlib.sha256(seed + (2 * i).to_bytes(4, "big")).digest()
    s1 = hashlib.sha256(seed + (2 * i + 1).to_bytes(4, "big")).digest()
    sk.append((s0, s1))
    pk.append((hashlib.sha256(s0).digest(), hashlib.sha256(s1).digest()))

print(n * 2 * 32)
# ==> 16384
print(n * 32)
# ==> 8192

Signing and verification at $n = 256$ follow the same pattern as the $n = 8$ case. Hash the message to a 256-bit digest, reveal one secret per bit, and verify by re-hashing:

import hashlib

seed = b"ch14-full"
n = 256

sk = []
pk = []
for i in range(n):
    s0 = hashlib.sha256(seed + (2 * i).to_bytes(4, "big")).digest()
    s1 = hashlib.sha256(seed + (2 * i + 1).to_bytes(4, "big")).digest()
    sk.append((s0, s1))
    pk.append((hashlib.sha256(s0).digest(), hashlib.sha256(s1).digest()))

def bit(digest, i):
    return (digest[i // 8] >> (7 - (i % 8))) & 1

message = b"The Encryptorium Book of PQC"
digest = hashlib.sha256(message).digest()

sig = [sk[i][bit(digest, i)] for i in range(n)]
ok = all(
    hashlib.sha256(sig[i]).digest() == pk[i][bit(digest, i)]
    for i in range(n)
)
print(ok)
# ==> True

Why “one-time” is load-bearing

Sign two different messages $m_1$ and $m_2$ under the same Lamport key. The first signature reveals $s_{d_{1,i}}^{(i)}$ for each bit position $i$, where $d_1 = H(m_1)$. The second reveals $s_{d_{2,i}}^{(i)}$. At every bit position where $d_{1,i} \neq d_{2,i}$, the adversary now holds both halves of the secret pair: $s_0^{(i)}$ and $s_1^{(i)}$. At positions where $d_{1,i} = d_{2,i}$, only one half is known.

The number of fully compromised positions equals the Hamming distance between $H(m_1)$ and $H(m_2)$. For two random 256-bit digests, the expected Hamming distance is 128.

import hashlib

seed = b"ch14-full"
n = 256

sk = []
pk = []
for i in range(n):
    s0 = hashlib.sha256(seed + (2 * i).to_bytes(4, "big")).digest()
    s1 = hashlib.sha256(seed + (2 * i + 1).to_bytes(4, "big")).digest()
    sk.append((s0, s1))
    pk.append((hashlib.sha256(s0).digest(), hashlib.sha256(s1).digest()))

def bit(digest, i):
    return (digest[i // 8] >> (7 - (i % 8))) & 1

m1 = b"first message"
m2 = b"second message"
d1 = hashlib.sha256(m1).digest()
d2 = hashlib.sha256(m2).digest()

sig1 = [sk[i][bit(d1, i)] for i in range(n)]
sig2 = [sk[i][bit(d2, i)] for i in range(n)]

hamming = sum(bin(a ^ b).count("1") for a, b in zip(d1, d2))
print(hamming)
# ==> 132

After two signatures, the adversary has both halves at 132 of 256 positions and one half at the remaining 124. To forge a signature on a third message $m_3$, the adversary needs $s_{d_{3,i}}^{(i)}$ at every position. At a fully compromised position, the adversary always has the needed half. At a partially compromised position, the adversary has the needed half only if $d_{3,i}$ matches the bit value already revealed by one of the two legitimate signatures.

For a random third digest, each partially compromised position has a $1/2$ probability of being forgeable (the adversary holds the needed half from whichever of $d_1$ or $d_2$ matched at that position). The probability of forging all 256 positions simultaneously is $(1)^{132} \cdot (1/2)^{124} = 2^{-124}$, which is negligible. The attack does not produce a complete forgery on a random target.

The attack does produce a complete forgery when the adversary can choose $m_3$ so that every partially compromised position aligns with the known half. At each of the 124 partially compromised positions, only one of the two bit values works. The adversary needs a message whose digest matches those 124 constrained bits. Finding such a message requires a partial-preimage search over $2^{124}$ candidates, which is computationally infeasible.

The practical lesson: do not sign two messages under the same Lamport key. Even one additional signature leaks enough structure to reduce the adversary’s work, and the leakage grows with each additional use.

Winternitz compression

Lamport treats each digest bit independently, which makes the signature 256 secrets long. The Winternitz one-time signature (WOTS) compresses the signature by encoding the digest in base $w$ instead of base 2 (Merkle, 1989). Each base-$w$ digit indexes a position along a hash chain of length $w - 1$: the signer reveals an intermediate chain value, and the verifier hashes forward to the endpoint and compares. With this chapter’s bit notation, the number of chains drops from $n$ bit-slots to roughly $\lceil n / \log_2 w \rceil$ (plus a small checksum). Each chain then costs up to $w - 1$ hash evaluations during signing and verification. Chapter 15 builds the WOTS+ variant that XMSS uses and walks the tradeoff between $w$, signature size, and computation cost.

Merkle tree at depth 3

A single Lamport keypair supports one signature. A Merkle tree turns $2^d$ one-time keypairs into a $2^d$-time scheme with a single published root (Merkle, 1989).

Construction. Generate $2^d$ Lamport keypairs. Serialize each public key and hash it to a 32-byte leaf: $\ell_i = H(\mathrm{pk}_i)$. Build a complete binary tree of depth $d$: each internal node is $H(\text{left child} \| \text{right child})$. The signer distributes the root as the public key.

The snippet below builds an 8-leaf tree ($d = 3$) from fixed leaf values and prints the root:

import hashlib

leaves = [hashlib.sha256(f"leaf-{i}".encode()).digest() for i in range(8)]

# Build the tree as a 1-indexed flat array of length 16.
# Indices 8..15 are leaves; indices 1..7 are internal nodes; index 0 is unused.
tree = [b""] * 16
for i in range(8):
    tree[8 + i] = leaves[i]
for i in range(7, 0, -1):
    tree[i] = hashlib.sha256(tree[2 * i] + tree[2 * i + 1]).digest()

root = tree[1]
print(root.hex()[:16])
# ==> 6e421edd382a1e45

The flat array uses $2 \cdot 2^d = 16$ slots: slot 0 is unused, the 8 leaves occupy slots 8 through 15, and the 7 internal nodes occupy slots 1 through 7. The root at index 1 is the hash of its two children at indices 2 and 3, which are in turn hashes of their children, down to the leaves. This toy hashes every node with one bare $H$; production schemes do not. FIPS 205 individualizes these computations with role-specific functions, a public seed, and a per-position address (ADRS), so a value computed for one position and role is not reusable in another (National Institute of Standards and Technology, 2024). Chapter 17 builds that addressing.

Authentication paths

To convince a verifier that a particular leaf belongs to the tree, the signer provides an authentication path: the $d$ sibling hashes along the path from the leaf to the root. The verifier starts from the leaf, hashes it with its sibling to recover the parent, hashes the parent with its sibling to recover the grandparent, and so on until reaching the root. If the recomputed root matches the published root, the leaf is authenticated.

For leaf 3 (zero-indexed) in the 8-leaf tree, the authentication path has three entries: the sibling at the leaf level, the sibling at level 1, and the sibling at level 2.

import hashlib

leaves = [hashlib.sha256(f"leaf-{i}".encode()).digest() for i in range(8)]
tree = [b""] * 16
for i in range(8):
    tree[8 + i] = leaves[i]
for i in range(7, 0, -1):
    tree[i] = hashlib.sha256(tree[2 * i] + tree[2 * i + 1]).digest()

# Extract the authentication path for leaf 3.
leaf_index = 3
node = 8 + leaf_index  # = 11
path = []
for _ in range(3):
    sibling = node ^ 1  # XOR flips the last bit to get the sibling index.
    path.append(tree[sibling])
    node //= 2  # Move to the parent.

# Verify the path by recomputing the root from the leaf upward.
current = leaves[3]
idx = leaf_index
for s in path:
    if idx % 2 == 0:
        current = hashlib.sha256(current + s).digest()
    else:
        current = hashlib.sha256(s + current).digest()
    idx //= 2

print(current == tree[1])
# ==> True

The diagram below shows a Merkle tree of depth 3 with 8 leaves ($L_0$ through $L_7$). The authentication path for leaf $L_3$ is marked in gold: three sibling nodes whose hashes the verifier needs. The verifier hashes $L_3$ with sibling $L_2$ to get node $N_{1}$. It hashes $N_1$ with sibling $N_0$ to get $N_3$, then $N_3$ with sibling $N_2$ to reach the root.

Figure 14.1. An eight-leaf Merkle tree of depth 3. The target leaf L3 is marked in teal; the authentication-path siblings L2, N0, and N2 are marked in gold. Recomputing the root from L3 and the three siblings takes three hash calls.

The authentication path for $L_3$ consists of three sibling hashes: $L_2$ at the leaf level, $N_0$ (the node above $L_0$ and $L_1$) at level 1, and $N_2$ (the node above $L_4$ through $L_7$) at level 2. The verifier recomputes the root in three hash calls and compares against the published root.

The path has exactly $d$ entries regardless of which leaf is chosen. At depth $d = 3$, the authentication path adds $3 \times 32 = 96$ bytes to the signature. At $d = 10$ (1,024 one-time keys), the overhead is $10 \times 32 = 320$ bytes. At $d = 20$ (roughly one million keys), it is $20 \times 32 = 640$ bytes. The logarithmic growth is why Merkle trees scale.

Interactive demo

An interactive version of this tree is at the Merkle authentication-path demo. Pick any leaf to watch its authentication path to the root, and change the tree depth to watch the path length track the logarithm of the leaf count.

The Merkle signature scheme

The full Merkle signature scheme (MSS) combines Lamport OTS with a Merkle tree (Merkle, 1989).

Key generation. Choose a tree depth $d$. Generate $2^d$ independent Lamport keypairs. Serialize each Lamport public key, hash the serialization to a 32-byte leaf, and build the Merkle tree. The MSS public key is the tree root (32 bytes). The MSS secret key is the collection of all $2^d$ Lamport secret keys plus the tree.

Signing. To sign the $j$-th message (with $j$ tracked by the signer as state), use the $j$-th Lamport keypair: Lamport-sign the message, then extract the authentication path for leaf $j$. The MSS signature is the tuple (Lamport signature, Lamport public key, authentication path) plus the leaf index.

Verification. Given the MSS root, the message, a Lamport signature, a Lamport public key, an authentication path, and a leaf index: first verify the Lamport signature against the provided Lamport public key. If it passes, hash the Lamport public key to recover the leaf and verify the authentication path against the root. Accept only if both checks pass.

import hashlib

def lamport_keygen(seed, n=256):
    sk, pk = [], []
    for i in range(n):
        s0 = hashlib.sha256(seed + (2 * i).to_bytes(4, "big")).digest()
        s1 = hashlib.sha256(seed + (2 * i + 1).to_bytes(4, "big")).digest()
        sk.append((s0, s1))
        pk.append((hashlib.sha256(s0).digest(), hashlib.sha256(s1).digest()))
    return sk, pk

def lamport_sign(sk, message):
    digest = hashlib.sha256(message).digest()
    return [sk[i][(digest[i // 8] >> (7 - (i % 8))) & 1] for i in range(len(sk))]

def lamport_verify(pk, message, sig):
    digest = hashlib.sha256(message).digest()
    return all(
        hashlib.sha256(sig[i]).digest() == pk[i][(digest[i // 8] >> (7 - (i % 8))) & 1]
        for i in range(len(pk))
    )

def serialize_pk(pk):
    return b"".join(h0 + h1 for h0, h1 in pk)

# MSS keygen at d = 3 (8 one-time keys).
d = 3
num_leaves = 1 << d
mss_seed = b"ch14-mss"

all_sk, all_pk, leaves = [], [], []
for j in range(num_leaves):
    sk_j, pk_j = lamport_keygen(mss_seed + j.to_bytes(4, "big"))
    all_sk.append(sk_j)
    all_pk.append(pk_j)
    leaves.append(hashlib.sha256(serialize_pk(pk_j)).digest())

tree = [b""] * (2 * num_leaves)
for i in range(num_leaves):
    tree[num_leaves + i] = leaves[i]
for i in range(num_leaves - 1, 0, -1):
    tree[i] = hashlib.sha256(tree[2 * i] + tree[2 * i + 1]).digest()

root = tree[1]

# MSS sign with leaf 0.
leaf_index = 0
sig_lamport = lamport_sign(all_sk[leaf_index], b"hello MSS")
pk_lamport = all_pk[leaf_index]

node = num_leaves + leaf_index
path = []
for _ in range(d):
    path.append(tree[node ^ 1])
    node //= 2

# MSS verify.
ok_lamport = lamport_verify(pk_lamport, b"hello MSS", sig_lamport)
leaf_hash = hashlib.sha256(serialize_pk(pk_lamport)).digest()
current = leaf_hash
idx = leaf_index
for s in path:
    if idx % 2 == 0:
        current = hashlib.sha256(current + s).digest()
    else:
        current = hashlib.sha256(s + current).digest()
    idx //= 2

print(ok_lamport and current == root)
# ==> True

In this textbook SHA-256-root construction, the MSS public key is 32 bytes regardless of $d$. An SLH-DSA public key is built differently, from a public seed and a root rather than a root alone, so it is $2n$ bytes. At category 1 that is 32 bytes, the same size as this construction’s, rising to 48 at category 3 and 64 at category 5 (National Institute of Standards and Technology, 2024). The signature size is $n \times 32 + n \times 2 \times 32 + d \times 32$ bytes: 8,192 bytes for the Lamport signature, 16,384 bytes for the Lamport public key, and $32d$ bytes for the authentication path. The leaf index adds a further $\lceil d/8 \rceil$ bytes, excluded from the totals below as negligible. At $d = 3$, the total MSS signature is 24,672 bytes. At $d = 20$, it is 25,216 bytes. The Lamport components dominate; the tree overhead is small.

Correctness. Every valid (leaf index, Lamport signature, Lamport public key, authentication path) tuple verifies against the root by construction. The Lamport signature is valid because the signer used the correct secret key. The authentication path is valid because the tree was built honestly from the Lamport public keys.

Security sketch. An adversary who forges an MSS signature has done one of two things. (1) It produced a valid Lamport signature for a leaf whose Lamport secret key it does not hold. This reduces to breaking Lamport’s one-time unforgeability, which reduces to inverting the hash on an unrevealed secret. (2) It produced a leaf and authentication path that recompute to the published root for a public key it controls. This requires a second preimage or a collision in the leaf hash or an internal node. So the textbook MSS argument needs the one-time unforgeability of Lamport together with second-preimage and collision resistance of the tree hash, assuming unambiguous, domain-separated encodings for leaves and internal nodes (Merkle, 1989). XMSS sharpens this by replacing the bare tree hash with addressed, tweakable hash calls, so its proof rests on weaker, more targeted properties than plain collision resistance (Hülsing et al., 2018). Chapter 18 sets out the corresponding proof framework for SLH-DSA.

The scheme is stateful: the signer must track which leaf indices have been used. Signing with the same leaf twice reduces to the two-signature Lamport forgery described under “Why one-time is load-bearing” above. The danger is not only losing the counter in memory. Restoring a virtual-machine snapshot, a database row, or an HSM backup can replay an already-used leaf index, which is why NIST SP 800-208 treats state management as security-critical for stateful schemes (Cooper et al., 2020). Chapter 15 walks XMSS (RFC 8391 (Hülsing et al., 2018)), which adds Winternitz compression and this state management. Chapter 16 builds FORS (a few-time signature scheme) and the hypertree structure. Chapter 17 assembles both into SLH-DSA (FIPS 205), which eliminates state entirely.

Cryptanalysis and known attacks

Two-signature forgery at the Lamport level

After two signatures on messages $m_1$ and $m_2$ under the same key, the adversary holds both secret halves at $h$ positions. The count $h$ equals the Hamming distance between $H(m_1)$ and $H(m_2)$. For random messages, $h \approx 128$.

To forge a signature on a chosen message $m_3$, the adversary needs $s_{d_{3,i}}^{(i)}$ at all 256 positions. At each of the $h$ fully compromised positions, both halves are available. At each of the $256 - h$ partially compromised positions, the adversary holds only one half. A random target message $m_3$ requires the known half at each partially compromised position with probability $1/2$. The expected number of positions where the adversary can produce the needed secret is $h + (256 - h)/2 = 128 + h/2$. For $h = 132$, that is $128 + 66 = 194$ positions, falling short of the 256 required for a complete forgery.

The residual classical hardness of forging all 256 positions after two signatures is $2^{256 - h}$ partial-preimage evaluations, which is $2^{124}$ for $h = 132$. Under Grover search the quantum cost is $2^{(256-h)/2} = 2^{62}$, below the $2^{64}$ Grover query count of the AES-128 key search that NIST’s category 1 is named for. That is a query comparison, not a category verdict, for the reason the table under “Grover’s impact on hash preimage security” gives. Either way, the key is degraded from the $2^{256}$ classical cost of inverting an unrevealed secret. Each additional signature leaks more positions. After $k$ signatures on random messages, the expected number of positions where both halves are known is $256 \cdot (1 - 2^{1-k})$. After $\log_2 256 + 1 = 9$ random signatures, nearly all positions are compromised.

That $2^{256}$ is the cost of inverting one unrevealed secret, not the unforgeability of the scheme. This construction signs $H(m)$ for an arbitrary $m$, so an adversary has a cheaper generic route that never touches the secret key. Find two messages with the same SHA-256 digest, at the birthday cost of about $2^{128}$ evaluations, have one signed, and present that signature on the other. Classical unforgeability here is therefore capped near $2^{128}$ from the outset, so the two-signature leak buys about four classical bits over a route already open against a fresh key. The quantum degradation to $2^{62}$ is the one that bites. SP 800-208 closes the classical route for LMS and XMSS by prepending a per-signature randomizer before hashing, which defeats anyone who cannot predict it but not the signer, who chooses it (Cooper et al., 2020).

Second-preimage attacks at the Merkle tree level

A second-preimage attack targets the leaf or an internal node. Each leaf is the digest $\ell_j = H(\mathrm{serialize}(\mathrm{pk}_j))$. Substituting a rogue public key $\mathrm{pk}'$ at position $j$ requires $H(\mathrm{serialize}(\mathrm{pk}')) = \ell_j$, or a second preimage of an internal node along the authenticated path. With either, the adversary signs under its own secret key. The classical cost is $O(2^{256})$ for SHA-256. Under Grover search, the quantum cost is $O(2^{128})$ ideal serial hash queries (Grover, 1996).

A collision attack is cheaper to mount but not automatically a forgery. Finding any pair of distinct inputs with the same internal hash costs $O(2^{128})$ classically for a 256-bit hash (birthday bound). A collision is only useful, though, if the adversary can embed it as a node on a valid path from a leaf it controls to the published root. SLH-DSA blunts the multi-target version by individualizing each tree and chain hash call with a per-position address (ADRS), a public seed, and role-specific hash functions (National Institute of Standards and Technology, 2024). Chapter 17 walks the details.

Grover’s impact on hash preimage security

The table below maps hash output size to preimage security under classical and quantum adversaries. The quantum column divides the exponent by two (Grover’s $O(\sqrt{N})$ bound). The last column is the AES key-length analogue in the query model: NIST defines categories 1, 3, and 5 by key search on AES-128, AES-192, and AES-256 (National Institute of Standards and Technology, 2016). A hash of $n$ bits pairs with the AES key of the same length because both cost $2^{n/2}$ Grover queries. That pairing is a query count, not a category claim. NIST prices its categories as gate counts under a depth limit, $2^{170} / \mathrm{MAXDEPTH}$ quantum gates for AES-128, and Jaques et al. cost explicit Grover circuits for each AES variant to refine those figures (Jaques et al., 2020). The table applies neither costing, so a concrete category comparison also needs the circuit cost of the hash oracle.

$n$	Classical preimage	Quantum preimage	AES analogue (query model)
128	$2^{128}$	$2^{64}$	AES-128 (category 1)
192	$2^{192}$	$2^{96}$	AES-192 (category 3)
256	$2^{256}$	$2^{128}$	AES-256 (category 5)
384	$2^{384}$	$2^{192}$	beyond AES-256
512	$2^{512}$	$2^{256}$	beyond AES-256

SLH-DSA places the quantum preimage cost at these levels for categories 1, 3, and 5. In this chapter’s bit notation those are 128-, 192-, and 256-bit hash outputs. FIPS 205 measures $n$ in bytes, so its parameter sets use $n = 16$, $n = 24$, and $n = 32$ (National Institute of Standards and Technology, 2024). Chapter 13 placed the lattice category floors in terms of BKZ block sizes. The hash-based floors are simpler: the quantum preimage query count of $2^{n/2}$ matches the Grover key-search query count on the corresponding AES variant.

Tradeoffs inside Part III

Lamport + Merkle is the simplest hash-based signature scheme and the largest. The rest of Part III progressively compresses and extends it.

• Lamport + Merkle (this chapter): secret key is $2^d$ Lamport keypairs, public key is 32 bytes (the root), signature is 24,672 bytes at $d = 3$ with 8,192 bytes from the Lamport OTS alone. Stateful: the signer must track which leaf index to use next.
• WOTS+ and XMSS (Chapter 15): Winternitz compression replaces the one-secret-per-bit Lamport structure with base-$w$ hash chains. At $w = 16$ with a 32-byte hash, the WOTS+ signature is 67 chain values (2,144 bytes), roughly 4x smaller than Lamport’s 8,192 bytes. XMSS (NIST SP 800-208) wraps WOTS+ in a Merkle tree. Still stateful.
• SLH-DSA / FIPS 205 (Chapter 17): the NIST hash-based signature standard. Eliminates state by signing the message digest with FORS (a few-time signature) and authenticating the FORS public key through a hypertree of XMSS/WOTS+ trees. Signatures range from 7,856 bytes (SLH-DSA-128s) to 49,856 bytes (SLH-DSA-256f) depending on the parameter set and fast/small tradeoff (National Institute of Standards and Technology, 2024). The security argument rests on hash-function and pseudorandom-function properties, not on algebraic assumptions such as factoring, discrete logarithms, lattices, or codes.

Exercises

1. Lamport keygen, sign, and verify at $n = 8$ by hand. Using the seed b"exercise-1" and the key generation pattern from the eight-bit example above, produce 8 secret pairs and 8 public-key hash pairs. Sign the message b"\x5C". The Lamport bits are taken from the SHA-256 digest of the message, not from the raw byte 0x5C. List the 8 revealed secrets (by index and bit value). Verify each by hashing and comparing against the public key.

2. Two-signature forgery at $n = 256$. Generate a Lamport keypair with seed b"exercise-2". Sign messages b"alpha" and b"beta" under the same key. Compute the Hamming distance between the two message digests. List five specific bit positions where the adversary now holds both secret halves. For the target message b"gamma", count how many of the 256 positions are forgeable using only the secrets from the two legitimate signatures.

3. Merkle root at $d = 3$. Given 8 leaf hashes computed as SHA256(f"ex3-leaf-{i}") for $i = 0, \ldots, 7$, build the Merkle tree by hand. State the root hash (first 8 hex characters). Extract the authentication path for leaf 5 and verify it by recomputing the root.

4. Grover bit-cost table. Fill in a table with columns (hash output bits $n$, classical preimage cost $2^n$, quantum preimage cost $2^{n/2}$, AES analogue in the query model) for $n \in \{128, 160, 192, 224, 256, 384, 512\}$. Pair each $n$ with the AES key length whose Grover key-search query count equals the hash’s quantum preimage query count, as the table in the chapter body does. A 160- or 224-bit output lies between two adjacent AES key lengths. State, for each $n$, whether the idealized query count is equal to, between, or above those of AES-128, AES-192, and AES-256, and say what a concrete NIST category comparison needs beyond the query count.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 14. A separate track, for rebuilding rather than reading: the package exercises/ch14-lamport stubs out the routines the chapter teaches, leaving the ones it prints in full already implemented. Run PQC_IMPL=exercises pytest tests/ch14 to grade your version against the suite that proves the reference one.

References

Aumasson, J.-P., Bernstein, D. J., Beullens, W., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.-L., Hülsing, A., Kampanakis, P., Kölbl, S., Lange, T., Lauridsen, M. M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., & Westerbaan, B. (2020). SPHINCS+: Submission to the NIST Post-Quantum Cryptography Standardization Process. NIST PQC Round 3 submission; SPHINCS+ specification v3, 1 October 2020. https://sphincs.org/data/sphincs+-round3-specification.pdf

Boneh, D., & Shoup, V. (2023). A Graduate Course in Applied Cryptography (v0.6). Free online textbook. https://toc.cryptobook.us/

Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum Cryptanalysis of Hash and Claw-Free Functions. LATIN ’98: Theoretical Informatics, 1380, 163–169. https://doi.org/10.1007/bfb0054319

Cooper, D., Apon, D., Dang, Q., Davidson, M., Dworkin, M., & Miller, C. (2020). Recommendation for Stateful Hash-Based Signature Schemes. NIST Special Publication 800-208. https://doi.org/10.6028/nist.sp.800-208

Goldwasser, S., Micali, S., & Rivest, R. L. (1988). A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2), 281–308. https://doi.org/10.1137/0217017

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. https://doi.org/10.1145/237814.237866

Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., & Mohaisen, A. (2018). XMSS: eXtended Merkle Signature Scheme. IETF RFC 8391. https://doi.org/10.17487/rfc8391

Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020). Implementing Grover oracles for quantum key search on AES and LowMC. Advances in Cryptology – EUROCRYPT 2020. https://doi.org/10.1007/978-3-030-45724-2_10

Lamport, L. (1979). Constructing Digital Signatures from a One Way Function. https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/

Merkle, R. C. (1989). A Certified Digital Signature. Advances in Cryptology – CRYPTO ’89, 435, 218–238. https://doi.org/10.1007/0-387-34805-0_21

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

National Institute of Standards and Technology. (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205