Hash-Based Signatures | Post-Quantum Cryptography

Overview

Hash-based signatures occupy a unique position in post-quantum cryptography: they are the only standardized digital signature family whose security rests entirely on the properties of a hash function. Every other post-quantum signature scheme — lattice-based (ML-DSA), code-based, multivariate — introduces additional structural assumptions that could, in principle, be broken by future mathematical or algorithmic advances. Hash-based signatures require only that the underlying hash function is preimage-resistant, second-preimage-resistant, and collision-resistant. If SHA-256 or SHAKE-256 remains secure, the signature scheme remains secure.

This minimal assumption set is why NIST included SLH-DSA (FIPS 205), based on SPHINCS+, as one of the three standardized post-quantum signature algorithms alongside ML-DSA (FIPS 204) and the forthcoming FN-DSA. It serves as the conservative backup — the algorithm you deploy when you need the highest confidence that no future cryptanalytic breakthrough will invalidate your signatures. The tradeoff is size: hash-based signatures are significantly larger than their lattice-based counterparts, making them impractical for some use cases but ideal for others.

This page traces the intellectual lineage from Lamport’s one-time signatures (1979) through Winternitz compression, Merkle trees, the stateful schemes XMSS and LMS, and finally to the stateless SLH-DSA standard. For background on NIST’s selection process, see NIST PQC Standardization Process. For quantum threats to classical signatures, see Classical Cryptography at Risk.

1. Why Hash-Based Signatures Are Special

The Assumption Hierarchy

Every cryptographic signature scheme relies on computational assumptions. The security confidence of a scheme is inversely proportional to the strength and number of assumptions it requires:

Scheme Family	Core Assumptions	Assumption Strength
RSA-PSS	Integer factorization is hard	Single, well-studied, broken by Shor
ECDSA	Elliptic curve discrete log is hard	Single, well-studied, broken by Shor
ML-DSA (Dilithium)	Module-LWE and Module-SIS are hard	Lattice problems; well-studied but younger
FN-DSA (Falcon)	NTRU lattice problem is hard	Structured lattice; fewer reduction results
Hash-based (SLH-DSA)	Hash function is secure	Minimal — decades of analysis on SHA/SHAKE

Hash functions are the most battle-tested primitives in cryptography. SHA-2 has been deployed since 2001 with no practical attacks against its full-round versions. The SHA-3 (Keccak) family, standardized in 2015, provides an entirely independent design. If either hash function family survives — and history strongly suggests both will — hash-based signatures remain secure against classical computers, quantum computers, and any future computational model.

No Algebraic Structure to Exploit

Lattice-based schemes rely on the hardness of problems in structured algebraic objects (polynomial rings, modules over rings). While no efficient algorithms are known for these problems, the algebraic structure provides a surface area for potential future attacks. Hash-based signatures have no algebraic structure whatsoever. The only operation is hashing. There is no ring, no lattice, no group — just a one-way function applied repeatedly. This makes cryptanalysis extraordinarily difficult: an attacker cannot exploit mathematical relationships between components because there are none.

Quantum Resistance by Design

Grover’s algorithm provides a generic quadratic speedup for searching unstructured spaces, which effectively halves the security level of any hash function. A 256-bit hash provides 128 bits of quantum security. This is well-understood, easily quantified, and trivially mitigated by choosing an appropriate output length. There is no quantum algorithm that provides a super-quadratic speedup for inverting hash functions, and the theoretical community widely believes none exists. For a detailed treatment of Grover’s algorithm and its implications, see Shor’s and Grover’s Algorithms.

2. Lamport Signatures: Where It All Began

The One-Time Signature Concept

Leslie Lamport introduced hash-based signatures in 1979 with a scheme of elegant simplicity. The idea: use the preimage resistance of a hash function to construct a signature that can be verified but not forged.

Key Generation (for signing a single n-bit message digest):

Generate 2n random secret values: sk[0][0], sk[0][1], sk[1][0], sk[1][1], ..., sk[n-1][0], sk[n-1][1]
Compute the public key by hashing each secret value: pk[i][b] = H(sk[i][b]) for all i and b ∈ {0, 1}
The public key is the set of all 2n hash values

Signing a message digest d = d₀d₁...d_{n-1}:

For each bit position i, reveal sk[i][d_i] — that is, if bit i of the digest is 0, reveal sk[i][0]; if it is 1, reveal sk[i][1].

Verification:

For each bit position i, check that H(sig[i]) == pk[i][d_i]. If all n checks pass, the signature is valid.

Why It Works

An attacker who wants to forge a signature on a different message would need to find a preimage for at least one hash value they have not seen — specifically, for some bit position where the forged message’s digest differs from the legitimate signature’s digest. This requires breaking the preimage resistance of H, which is computationally infeasible for a secure hash function.

Why Lamport Is Impractical Alone

The limitations are severe:

One-time use only: Each key pair can sign exactly one message. Signing a second message with the same key leaks additional secret values, potentially enabling forgery. If both sk[i][0] and sk[i][1] are revealed for any position i, an attacker can forge signatures on messages that differ at position i.
Enormous key and signature sizes: For a 256-bit security level, the private key is 2 × 256 × 256 bits = 16 KB, the public key is also 16 KB, and each signature is 256 × 256 bits = 8 KB.
No key reuse mechanism: There is no built-in way to sign multiple messages with a single public key.

Despite these limitations, Lamport signatures are the conceptual foundation for all subsequent hash-based signature schemes. Every improvement that follows is a technique for making Lamport-style one-time signatures smaller, faster, or reusable.

3. WOTS+: The Winternitz Time-Memory Tradeoff

Compressing Lamport with Hash Chains

The Winternitz One-Time Signature Plus (WOTS+) scheme, formalized by Hülsing in 2013, dramatically reduces the size of Lamport signatures by replacing individual bit signing with base-w digit signing using hash chains.

Instead of signing each bit independently, WOTS+ groups the message digest into digits in base w (the Winternitz parameter) and signs each digit by iterating a hash function along a chain.

Key Generation:

Choose Winternitz parameter w (typically 4, 16, or 256)
Compute len₁ = ⌈n / log₂(w)⌉ — the number of base-w digits needed to represent the n-bit digest
Compute len₂ = ⌊log₂(len₁ × (w - 1)) / log₂(w)⌋ + 1 — checksum digits to prevent forgery
Set len = len₁ + len₂
Generate len random secret values: sk[0], sk[1], ..., sk[len-1]
For each secret value, compute the end of the hash chain: pk[i] = H^{w-1}(sk[i]) — that is, apply H iteratively w-1 times

Signing a message digest:

Convert the digest to base-w digits: d₀, d₁, ..., d_{len₁-1}
Compute a checksum over those digits and convert it to base-w: c₀, c₁, ..., c_{len₂-1}
For each digit dᵢ, compute sig[i] = H^{dᵢ}(sk[i]) — hash the secret value dᵢ times

Verification:

For each signature component sig[i] with corresponding digit dᵢ, compute H^{w-1-dᵢ}(sig[i]) and check that it equals pk[i]. The verifier “completes” the hash chain.

The Winternitz Parameter Tradeoff

The parameter w controls a direct tradeoff between signature size and computation:

w	Digits (len₁, 256-bit)	Chain Length	Signature Size	Hash Evaluations (Sign)
4	128	3	~4.3 KB	~256
16	64	15	~2.1 KB	~480
256	32	255	~1.1 KB	~4,080

Higher w means fewer digits (smaller signatures) but longer chains (more hash evaluations). The ”+” in WOTS+ refers to the use of bitmasks and tweakable hash functions that provide tighter security reductions compared to the original WOTS scheme.

The Checksum: Preventing Forgery by Extension

Without the checksum, an attacker could trivially forge signatures. Given a signature on a message with digit value dᵢ = 5, the attacker can compute H(sig[i]) to obtain a valid signature component for digit value 6. The attacker can always extend a hash chain forward but never reverse it.

The checksum prevents this: it is defined as C = Σ(w - 1 - dᵢ) over all message digits. If any message digit increases (which would allow chain extension), the checksum decreases, requiring the attacker to reverse a hash chain on at least one checksum digit — which requires breaking preimage resistance.

4. Merkle Tree Signatures: From One-Time to Many-Time

Ralph Merkle’s Insight

In 1979, Ralph Merkle proposed using a binary hash tree to authenticate many one-time signature public keys under a single root. This transforms a one-time scheme into a many-time scheme without introducing any new cryptographic assumptions.

graph TD
    Root["Root (Public Key)"]
    H01["H(H₀ ∥ H₁)"]
    H23["H(H₂ ∥ H₃)"]
    H0["H(OTS pk₀)"]
    H1["H(OTS pk₁)"]
    H2["H(OTS pk₂)"]
    H3["H(OTS pk₃)"]
    OTS0["OTS Key Pair 0"]
    OTS1["OTS Key Pair 1"]
    OTS2["OTS Key Pair 2"]
    OTS3["OTS Key Pair 3"]

    Root --> H01
    Root --> H23
    H01 --> H0
    H01 --> H1
    H23 --> H2
    H23 --> H3
    H0 --> OTS0
    H1 --> OTS1
    H2 --> OTS2
    H3 --> OTS3

    style Root fill:#1a1a2e,stroke:#e94560,color:#eee
    style H01 fill:#1a1a2e,stroke:#0f3460,color:#eee
    style H23 fill:#1a1a2e,stroke:#0f3460,color:#eee
    style H0 fill:#16213e,stroke:#0f3460,color:#eee
    style H1 fill:#16213e,stroke:#0f3460,color:#eee
    style H2 fill:#16213e,stroke:#0f3460,color:#eee
    style H3 fill:#16213e,stroke:#0f3460,color:#eee
    style OTS0 fill:#0f3460,stroke:#16213e,color:#eee
    style OTS1 fill:#0f3460,stroke:#16213e,color:#eee
    style OTS2 fill:#0f3460,stroke:#16213e,color:#eee
    style OTS3 fill:#0f3460,stroke:#16213e,color:#eee

Construction (for a tree of height h, supporting 2^h signatures):

Generate 2^h WOTS+ key pairs
Hash each OTS public key to produce a leaf node
Build the tree bottom-up: each internal node is the hash of its two children
The root of the tree is the single public key

Signing the i-th message:

Use OTS key pair i to produce a one-time signature on the message
Include the authentication path: the h sibling nodes along the path from leaf i to the root

Verification:

Verify the OTS signature against the OTS public key
Hash the OTS public key to get the leaf node
Use the authentication path to reconstruct the root, hashing upward through the tree
Compare the reconstructed root to the known public key

Authentication Path Example

For a tree of height 3 (8 leaves), signing with leaf 5 requires siblings at nodes 4, {6,7}‘s parent, and {0,1,2,3}‘s parent. The verifier reconstructs:

leaf₅ → H(leaf₄ ∥ leaf₅) → H(H(leaf₄ ∥ leaf₅) ∥ H(leaf₆ ∥ leaf₇)) → Root

The authentication path contains exactly h hash values, keeping the overhead logarithmic in the number of supported signatures. For a tree of height 20 (supporting roughly 1 million signatures), each signature includes only 20 hash values as authentication overhead — an elegant demonstration of the power of binary trees for amortizing one-time constructions.

The verification cost is also logarithmic: the verifier performs one OTS verification plus h hash computations to reconstruct the root. This makes Merkle tree signature verification extremely fast — typically under a millisecond even for large trees.

Tree Traversal Optimization

Naively computing the authentication path for each signature requires traversing the full tree, which is expensive for large trees. Several algorithms optimize this:

Classic Merkle traversal: O(h) space and O(1) amortized hash computations per signature by caching upcoming authentication nodes
BDS (Buchmann-Dahmen-Szydlo) traversal: Reduces space requirements to O(h²/2) while maintaining O(1) amortized computation
Fractal Merkle trees: Multi-level caching strategy for very large trees

5. Stateful Schemes: XMSS and LMS

XMSS (Extended Merkle Signature Scheme)

XMSS, standardized in RFC 8391 (2018), extends the basic Merkle tree scheme with several improvements:

WOTS+ as the OTS layer: Uses the improved Winternitz scheme with bitmasks
L-trees: Compresses the multi-element WOTS+ public key into a single leaf value using a secondary hash tree
Tweakable hash functions: Each hash call includes a unique address (position in the tree, chain index, hash step) to domain-separate all hash evaluations, preventing multi-target attacks
XMSS^MT (Multi-Tree): A hierarchical extension that uses a tree of trees, reducing key generation time from O(2^h) to O(2^{h/d}) where d is the number of tree layers

XMSS Parameters:

Parameter Set	Hash	Tree Height	Sig Size	Pk Size	Signatures Available
XMSS-SHA2_10_256	SHA-256	10	2,500 B	64 B	1,024
XMSS-SHA2_16_256	SHA-256	16	2,692 B	64 B	65,536
XMSS-SHA2_20_256	SHA-256	20	2,820 B	64 B	1,048,576
XMSS-SHAKE_10_256	SHAKE128	10	2,500 B	64 B	1,024
XMSS-SHAKE_20_256	SHAKE128	20	2,820 B	64 B	1,048,576

LMS/HSS (Leighton-Micali Signatures)

LMS, standardized in RFC 8554 (2019), takes a slightly different approach from XMSS but achieves similar goals:

Uses LM-OTS (Leighton-Micali One-Time Signature) as the base OTS scheme — functionally similar to WOTS+ but with a different construction and parameter naming
The Merkle tree construction is essentially the same as XMSS
HSS (Hierarchical Signature System) provides multi-tree functionality analogous to XMSS^MT, chaining multiple LMS trees to increase the total number of available signatures

LMS Parameters:

Parameter Set	Hash	Tree Height	Sig Size	Pk Size	Signatures Available
LMS_SHA256_M32_H5	SHA-256	5	1,620 B	56 B	32
LMS_SHA256_M32_H10	SHA-256	10	1,780 B	56 B	1,024
LMS_SHA256_M32_H15	SHA-256	15	1,940 B	56 B	32,768
LMS_SHA256_M32_H20	SHA-256	20	2,100 B	56 B	1,048,576
LMS_SHA256_M32_H25	SHA-256	25	2,260 B	56 B	33,554,432

The State Management Problem

Both XMSS and LMS are stateful: the signer must maintain a counter tracking which leaf index has been used, and must never reuse a leaf index. Reusing a one-time key pair allows an attacker to forge signatures. This creates a critical operational requirement:

Why state management is dangerous:

Crash recovery: If the system crashes after signing but before persisting the updated state, the index may be reused on restart
VM cloning/snapshots: Restoring a virtual machine snapshot rewinds the state counter, causing index reuse
Distributed systems: If multiple instances share a key, coordinating state across nodes is extremely difficult. Standard distributed consensus protocols add latency and complexity
Backup/restore: Restoring from backup rolls back the state counter
Hardware failure: If the state is stored on a single device that fails, the key is lost

Mitigation strategies:

Reserve index ranges: Pre-advance the counter by a batch size (e.g., 1000) and persist the advanced value. If the system crashes, at most 1000 indices are wasted but none are reused
Hardware Security Modules (HSMs): Use tamper-resistant hardware with atomic state updates. Modern HSMs from vendors like Thales and Entrust support XMSS/LMS with built-in state management
Dedicated signing servers: Centralize signing operations on a single, carefully managed node with battery-backed write caches and journaling

When Stateful Schemes Are Acceptable

Despite the state management burden, stateful schemes offer smaller signatures and faster operations than stateless alternatives, making them ideal for specific use cases:

Root CA certificates: A root CA signs certificates infrequently (perhaps a few hundred times over its lifetime). A single HSM with a tree height of 20 provides over a million signatures — far more than needed. The signing is done on a single, air-gapped machine with careful state management
Firmware signing: A firmware vendor signs releases on a dedicated build server. The signing frequency is low and predictable, and the key can be stored in an HSM
Code signing: Similar to firmware signing — centralized, low-frequency, HSM-backed
Trust anchor updates: Signing root key bundles, CRL updates, or DNSSEC zone keys
Long-lived document signatures: Legal, regulatory, or archival signatures where the signing ceremony is a deliberate, controlled process

NIST published SP 800-208 in 2020, providing recommendations for stateful hash-based signature schemes (XMSS and LMS) and explicitly warning that these schemes are only appropriate for environments where state can be reliably managed.

6. SLH-DSA (FIPS 205): The Stateless Solution

From SPHINCS+ to SLH-DSA

SPHINCS+ was submitted to the NIST PQC competition by a team led by Daniel J. Bernstein and was selected in July 2022 as one of the three standardized signature algorithms. NIST published it as FIPS 205 in August 2024 under the name SLH-DSA (Stateless Hash-Based Digital Signature Algorithm).

The fundamental innovation of SPHINCS+ is eliminating state entirely by combining three ideas:

FORS (Forest of Random Subsets): A few-time signature scheme that replaces WOTS+ at the bottom layer
A hypertree of WOTS+ Merkle trees: Authenticates the FORS public keys
Randomized message indexing: Maps each message to a random position in the hypertree, amortizing the few-time security of FORS across the entire tree

FORS: Forest of Random Subsets

FORS is a few-time signature scheme designed specifically for use within the SPHINCS+/SLH-DSA construction. Unlike WOTS+ (which is one-time), FORS can tolerate a bounded number of signatures without catastrophic security loss.

How FORS works:

The signer maintains k binary trees, each with 2^a leaves (where a is a parameter called the “tree height” and k is the number of trees)
To sign a message, the message digest is split into k segments of a bits each
Each a-bit segment selects one leaf from the corresponding tree
The signature consists of the k selected leaf values plus their authentication paths within their respective trees
The FORS public key is the hash of the k tree roots

Why FORS tolerates multiple signatures:

Each signing operation reveals only k out of k × 2^a total leaf values. An attacker can only forge a signature if, for every one of the k trees, the target message selects a leaf that was already revealed in a previous signature. The probability of this happening grows slowly with the number of signatures, providing quantifiable security degradation rather than immediate catastrophic failure.

For SLH-DSA parameters, the FORS construction provides security even after 2^{h/d} signatures at any single FORS position, where h is the total hypertree height and d is the number of layers.

The security analysis of FORS is probabilistic. With k trees of 2^a leaves each, the probability that an attacker can forge after observing q signatures at the same FORS position is bounded by:

P_forge ≤ (q / 2^a)^k

For typical SLH-DSA parameters (k=14, a=12), even after 16 signatures at the same FORS instance (which is extremely unlikely given random index selection), the forgery probability is approximately (16/4096)^14 = 2^{-112} — still well below the target security level.

The Hypertree Structure

The hypertree is a tree of Merkle trees, organized into d layers. Each layer contains WOTS+ Merkle trees of height h/d.

graph TD
    subgraph "Layer d (Top)"
        TopRoot["Top Tree Root<br/>(Public Key)"]
        TopTree["WOTS+ Merkle Tree<br/>Height h/d"]
    end

    subgraph "Layer d-1"
        Mid1["WOTS+ Merkle Tree"]
        Mid2["WOTS+ Merkle Tree"]
        Mid3["..."]
    end

    subgraph "Layer 1"
        Bot1["WOTS+ Merkle Tree"]
        Bot2["WOTS+ Merkle Tree"]
        Bot3["WOTS+ Merkle Tree"]
        Bot4["WOTS+ Merkle Tree"]
        Bot5["..."]
    end

    subgraph "Layer 0 (FORS)"
        FORS1["FORS Instance"]
        FORS2["FORS Instance"]
        FORS3["FORS Instance"]
        FORS4["FORS Instance"]
        FORS5["FORS Instance"]
        FORS6["FORS Instance"]
        FORS7["..."]
    end

    TopRoot --> TopTree
    TopTree --> Mid1
    TopTree --> Mid2
    TopTree --> Mid3
    Mid1 --> Bot1
    Mid1 --> Bot2
    Mid2 --> Bot3
    Mid2 --> Bot4
    Mid3 --> Bot5
    Bot1 --> FORS1
    Bot1 --> FORS2
    Bot2 --> FORS3
    Bot2 --> FORS4
    Bot3 --> FORS5
    Bot3 --> FORS6
    Bot4 --> FORS7

    style TopRoot fill:#1a1a2e,stroke:#e94560,color:#eee
    style TopTree fill:#1a1a2e,stroke:#e94560,color:#eee
    style Mid1 fill:#1a1a2e,stroke:#0f3460,color:#eee
    style Mid2 fill:#1a1a2e,stroke:#0f3460,color:#eee
    style Mid3 fill:#1a1a2e,stroke:#0f3460,color:#eee
    style Bot1 fill:#16213e,stroke:#0f3460,color:#eee
    style Bot2 fill:#16213e,stroke:#0f3460,color:#eee
    style Bot3 fill:#16213e,stroke:#0f3460,color:#eee
    style Bot4 fill:#16213e,stroke:#0f3460,color:#eee
    style Bot5 fill:#16213e,stroke:#0f3460,color:#eee
    style FORS1 fill:#0f3460,stroke:#16213e,color:#eee
    style FORS2 fill:#0f3460,stroke:#16213e,color:#eee
    style FORS3 fill:#0f3460,stroke:#16213e,color:#eee
    style FORS4 fill:#0f3460,stroke:#16213e,color:#eee
    style FORS5 fill:#0f3460,stroke:#16213e,color:#eee
    style FORS6 fill:#0f3460,stroke:#16213e,color:#eee
    style FORS7 fill:#0f3460,stroke:#16213e,color:#eee

Signing process in the hypertree:

Hash the message with a randomizer to produce an index and a message digest
The index selects a specific FORS instance at the bottom of the hypertree
Sign the message digest using that FORS instance
The FORS public key becomes the message signed by the WOTS+ instance in layer 1 above it
Each layer’s WOTS+ public key is authenticated by the Merkle tree at that layer, and the tree root is signed by the WOTS+ instance in the next layer up
This continues until the top-level tree, whose root is the SLH-DSA public key

The signature contains:

The randomizer value
The FORS signature (k leaf values + k authentication paths)
d WOTS+ signatures, one per hypertree layer
d authentication paths, one per Merkle tree traversed

SLH-DSA Parameter Sets

FIPS 205 defines twelve parameter sets across three security levels and two optimization targets:

Parameter Set	Security Level	n (bytes)	h	d	k	a	Sig Size	Pk Size	Sk Size
SLH-DSA-SHA2-128s	1 (128-bit)	16	63	7	14	12	7,856 B	32 B	64 B
SLH-DSA-SHA2-128f	1 (128-bit)	16	66	22	33	6	17,088 B	32 B	64 B
SLH-DSA-SHA2-192s	3 (192-bit)	24	63	7	17	14	16,224 B	48 B	96 B
SLH-DSA-SHA2-192f	3 (192-bit)	24	66	22	33	8	35,664 B	48 B	96 B
SLH-DSA-SHA2-256s	5 (256-bit)	32	64	8	22	14	29,792 B	64 B	128 B
SLH-DSA-SHA2-256f	5 (256-bit)	32	68	17	35	9	49,856 B	64 B	128 B
SLH-DSA-SHAKE-128s	1 (128-bit)	16	63	7	14	12	7,856 B	32 B	64 B
SLH-DSA-SHAKE-128f	1 (128-bit)	16	66	22	33	6	17,088 B	32 B	64 B
SLH-DSA-SHAKE-192s	3 (192-bit)	24	63	7	17	14	16,224 B	48 B	96 B
SLH-DSA-SHAKE-192f	3 (192-bit)	24	66	22	33	8	35,664 B	48 B	96 B
SLH-DSA-SHAKE-256s	5 (256-bit)	32	64	8	22	14	29,792 B	64 B	128 B
SLH-DSA-SHAKE-256f	5 (256-bit)	32	68	17	35	9	49,856 B	64 B	128 B

Parameter definitions:

n: Security parameter (hash output length in bytes)
h: Total hypertree height
d: Number of hypertree layers (each subtree has height h/d)
k: Number of FORS trees
a: Height of each FORS tree (each tree has 2^a leaves)

The “s” vs “f” Tradeoff

The suffixes s (small) and f (fast) represent fundamentally different optimization targets:

“s” (Small Signature) Parameter Sets:

Fewer hypertree layers (d = 7-8), meaning taller subtrees
Fewer but larger FORS trees (high a, moderate k)
Result: smaller signatures but slower signing and verification
Signing requires traversing fewer but taller trees, with more hash evaluations per tree

“f” (Fast) Parameter Sets:

More hypertree layers (d = 17-22), meaning shorter subtrees
More but smaller FORS trees (low a, high k)
Result: larger signatures but faster signing and verification
More WOTS+ signatures are included (one per layer), increasing size, but each subtree traversal is faster

Performance comparison (approximate, single-threaded, reference implementation):

Parameter Set	Key Gen	Sign	Verify	Sig Size
SLH-DSA-128s	~7 ms	~120 ms	~5 ms	7,856 B
SLH-DSA-128f	~0.3 ms	~6 ms	~0.4 ms	17,088 B
SLH-DSA-192s	~12 ms	~210 ms	~8 ms	16,224 B
SLH-DSA-192f	~0.5 ms	~10 ms	~0.6 ms	35,664 B
SLH-DSA-256s	~25 ms	~400 ms	~12 ms	29,792 B
SLH-DSA-256f	~0.8 ms	~15 ms	~0.9 ms	49,856 B

The “f” variants are roughly 20x faster for signing but produce signatures roughly 2x larger. The choice depends on whether bandwidth or computational latency is the primary constraint.

Stateless Operation: How It Works

The critical insight that makes SLH-DSA stateless: instead of maintaining a counter to select the next unused FORS instance, the scheme derives the FORS index from the message itself (combined with a random value). Specifically:

Generate a random value opt_rand (or use a deterministic pseudorandom value derived from the secret key and message)
Compute R = PRF(sk_prf, opt_rand, message) — a pseudorandom value unique to this signing operation
Hash R ∥ pk_seed ∥ pk_root ∥ message to produce an index idx and a message digest md
Use idx to select the FORS instance in the hypertree
Sign md with that FORS instance

Because R is freshly random (or deterministically unique) for each signing operation, the same FORS instance is selected with negligible probability. Even if collisions occur (two messages map to the same FORS instance), the security of FORS degrades gracefully — it is designed to tolerate a bounded number of signatures.

7. The Signature Size Problem

Comparative Analysis

Hash-based signatures are dramatically larger than both classical and lattice-based alternatives. This is the primary practical limitation:

Scheme	Type	Security Level	Public Key	Signature Size	Total (Pk + Sig)
ECDSA P-256	Classical	~128-bit	64 B	64 B	128 B
RSA-2048	Classical	~112-bit	256 B	256 B	512 B
Ed25519	Classical	~128-bit	32 B	64 B	96 B
ML-DSA-44	Lattice (PQ)	1 (128-bit)	1,312 B	2,420 B	3,732 B
ML-DSA-65	Lattice (PQ)	3 (192-bit)	1,952 B	3,309 B	5,261 B
ML-DSA-87	Lattice (PQ)	5 (256-bit)	2,592 B	4,627 B	7,219 B
SLH-DSA-128s	Hash (PQ)	1 (128-bit)	32 B	7,856 B	7,888 B
SLH-DSA-128f	Hash (PQ)	1 (128-bit)	32 B	17,088 B	17,120 B
SLH-DSA-256s	Hash (PQ)	5 (256-bit)	64 B	29,792 B	29,856 B
SLH-DSA-256f	Hash (PQ)	5 (256-bit)	64 B	49,856 B	49,920 B
XMSS-SHA2_20_256	Hash, Stateful (PQ)	~128-bit	64 B	2,820 B	2,884 B
LMS_SHA256_M32_H20	Hash, Stateful (PQ)	~128-bit	56 B	2,100 B	2,156 B

Key observations:

SLH-DSA-128s signatures are 123x larger than ECDSA P-256 signatures
SLH-DSA-256f signatures are 780x larger than Ed25519 signatures
Even at the same security level, SLH-DSA-128s is 3.2x larger than ML-DSA-44
Stateful schemes (XMSS, LMS) offer a middle ground — larger than lattice-based but much smaller than stateless hash-based
Public keys are tiny for all hash-based schemes — the size problem is entirely in signatures
At security level 5, the gap narrows: SLH-DSA-256s is ~6.4x larger than ML-DSA-87, not an order of magnitude
The combined public key + signature size for SLH-DSA-128s (~7.9 KB) is comparable to a small JPEG image — context matters when evaluating “large”

To put this in network terms: at 1 Mbps (a slow cellular connection), transmitting an SLH-DSA-128s signature takes approximately 63 milliseconds. At 100 Mbps (typical broadband), it takes 0.63 milliseconds. The size overhead is measurable but often not the bottleneck in real-world systems.

Where Size Matters

The signature size overhead rules out SLH-DSA for several use cases:

TLS handshakes: A TLS 1.3 handshake typically includes 2-3 signatures in the certificate chain. With SLH-DSA-128f, this adds ~50 KB to the handshake — problematic for constrained networks and adds measurable latency
Certificate Transparency logs: Billions of signed certificate timestamps (SCTs) would require orders of magnitude more storage
Blockchain transactions: On-chain signature size directly affects transaction fees and block utilization
IoT with bandwidth constraints: Devices on LoRaWAN, Zigbee, or satellite links may not have the bandwidth for multi-KB signatures

Where Size Does Not Matter

Conversely, many critical use cases are insensitive to signature size:

Root CA certificates: Signed once, verified rarely, stored in trust stores with ample capacity
Firmware images: The signature overhead of 8-50 KB is negligible relative to firmware images of megabytes or gigabytes
Code signing: Similar to firmware — the signed artifact dwarfs the signature
Document signing: PDFs and legal documents are typically kilobytes to megabytes; an additional 8-50 KB is irrelevant
DNSSEC root zone signing: Zone files are already large; root key signatures are verified infrequently

8. Use Cases and Deployment Guidance

Root CA and Trust Anchor Signing

Hash-based signatures are ideal for root certificate authorities and trust anchors:

Maximum security confidence: Root CA keys protect entire certificate hierarchies for decades. The minimal-assumption security of hash-based signatures provides the highest possible confidence that these keys will not be compromised by future cryptanalytic breakthroughs
Low signing frequency: A root CA may sign only a handful of intermediate CA certificates per year. Even stateful schemes are viable at this rate
Size irrelevance: Root certificates are cached in trust stores, not transmitted per-connection
Offline signing: Root CA signing ceremonies are conducted on air-gapped HSMs, eliminating the distributed state management problem for stateful schemes

Recommended approach: Use LMS/HSS (stateful) with an HSM for root CA operations where state can be guaranteed, or SLH-DSA-128s (stateless) if HSM state management is a concern.

Firmware and Software Signing

Firmware signing benefits from hash-based signatures for similar reasons:

The signature is verified once during installation or boot, not during high-throughput operations
The firmware image size makes signature overhead irrelevant
Long-lived firmware in deployed devices (vehicles, industrial control systems, medical devices) may need to be verifiable for 20+ years
The conservative security of hash-based signatures protects against the possibility that lattice problems are broken before the device’s end-of-life

Hybrid Deployment Strategy

For environments that need both performance and conservative security, a hybrid approach combines a fast lattice-based signature with a hash-based signature:

hybrid_signature = ML-DSA-65(message) ∥ SLH-DSA-128s(message)

The verifier checks both signatures. Security holds if either underlying scheme is secure. This provides the performance of ML-DSA for day-to-day operations with the conservative guarantee of SLH-DSA as a safety net. The total overhead is roughly 3,309 + 7,856 = ~11 KB per signature — acceptable for many applications.

NIST has signaled support for hybrid/composite signature approaches, and the IETF has active work on composite signature formats in X.509 certificates (draft-ounsworth-pq-composite-sigs).

Long-Lived Document Signatures

Documents that must remain verifiable for decades — legal contracts, patent filings, regulatory submissions, archival records — benefit from the most conservative signature available. SLH-DSA provides this guarantee: even if quantum computers break lattice problems (an unlikely but non-zero possibility), hash-based signatures remain valid.

Consider the lifecycle: a 30-year mortgage signed in 2026 must remain legally verifiable until 2056. A patent filing must be attributable for 20 years. Regulatory submissions to the FDA or SEC may be referenced in litigation decades later. For these use cases, the 8-50 KB overhead of an SLH-DSA signature is a negligible cost for the strongest available guarantee of long-term integrity.

DNSSEC and Trust Infrastructure

DNSSEC root zone signing is another compelling target. The root zone key signing key (KSK) protects the entire DNS hierarchy. It is signed infrequently (the root KSK has been rolled only once, in 2018) and the signature is cached by resolvers worldwide. A hash-based root KSK signature would add minimal overhead to the root zone while providing post-quantum security for the foundation of DNS authentication.

Similarly, Certificate Transparency (CT) log operators that sign Signed Tree Heads (STHs) could adopt SLH-DSA for these critical trust anchors while continuing to use ML-DSA for individual Signed Certificate Timestamps (SCTs) where throughput matters.

9. Real-World Deployment Status

Early Adopters

Several organizations have begun deploying hash-based signatures in production:

NIST’s own NCCoE: The National Cybersecurity Center of Excellence has published migration guides that prioritize hash-based signatures for firmware and root CA use cases
German BSI: The German Federal Office for Information Security (BSI) has recommended XMSS for long-term signature applications since 2020 and endorses SLH-DSA as part of their post-quantum guidance
U.S. CNSA 2.0: The NSA’s CNSA 2.0 suite includes LMS and XMSS for software and firmware signing, with a 2025 target for adoption in national security systems
Google: Has experimented with SPHINCS+ in Certificate Transparency and internal signing infrastructure
Cloudflare: Has conducted experiments with post-quantum signatures in TLS, including SLH-DSA measurements to characterize the bandwidth impact

Standardization Timeline

Date	Milestone
1979	Lamport and Merkle propose hash-based signatures
2011	XMSS proposed by Buchmann, Dahmen, and Hülsing
2013	WOTS+ formalized with tight security proofs
2017	SPHINCS+ submitted to NIST PQC competition
2018	XMSS standardized in RFC 8391
2019	LMS/HSS standardized in RFC 8554
2020	NIST SP 800-208 published for stateful HBS guidance
2022	SPHINCS+ selected by NIST as one of three signature standards
2024	FIPS 205 (SLH-DSA) published in final form
2025-2026	Library implementations maturing; early production deployments

10. Implementation Considerations

Side-Channel Resistance

Hash-based signatures have a natural advantage in side-channel resistance compared to lattice-based schemes. The primary operation — hash function evaluation — is well-studied for constant-time implementation. There are no polynomial multiplications, no Gaussian sampling, and no rejection sampling loops that might leak timing information.

However, implementers must still be careful:

Secret index in stateful schemes: The current leaf index in XMSS/LMS must not be leaked via timing or power analysis
WOTS+ chain computation: If an attacker can observe how many hash iterations are performed for each chain, they learn the digit values, which partially reveals the message digest
FORS leaf selection: The indices selected by FORS correspond to the message, so the access pattern must not be observable

Constant-time hash implementations (available in most modern crypto libraries) and standard cache-timing mitigations address these concerns.

Choosing the Right Scheme

Decision framework for selecting a hash-based signature scheme:

Use LMS/HSS (stateful) when:

Signing is centralized on a single HSM or dedicated server
The number of signatures over the key’s lifetime is bounded and predictable
You need the smallest possible hash-based signatures (~2 KB)
You can guarantee state will never be rewound (no VM snapshots, no backup restoration without key rotation)

Use SLH-DSA-*s (stateless, small) when:

Bandwidth is limited but signing speed is not critical
You want the most conservative security with manageable signature sizes (~8-30 KB)
Signing occurs at a moderate rate (not thousands per second)

Use SLH-DSA-*f (stateless, fast) when:

Signing speed matters more than signature size
You have sufficient bandwidth for larger signatures (~17-50 KB)
Bulk signing operations are needed (batch firmware signing, CI/CD pipelines)

Use ML-DSA instead when:

Signature size must be under 5 KB
High-throughput signing/verification is required (TLS, real-time protocols)
You accept the (minimal) additional risk of lattice assumption dependency

Library Support

Major cryptographic libraries with hash-based signature support (as of early 2026):

Library	SLH-DSA	XMSS	LMS	Notes
liboqs (Open Quantum Safe)	Yes	Yes	Yes	Reference implementations, C
Bouncy Castle	Yes	Yes	Yes	Java and C#
wolfSSL	Yes	No	Yes	Embedded-focused
PQClean	Yes	No	No	Clean C reference code
libsodium	Planned	No	No	Popular, not yet released
OpenSSL 3.5+	Yes	No	Yes	Via oqs-provider or native
NSS (Mozilla)	In progress	No	No	Firefox integration planned

11. Advanced Topics

Multi-Target Attack Resistance

A subtle but important consideration: in the standard hash-based signature model, an attacker targets a specific public key. But in real-world deployments with millions of signers, an attacker may succeed if they break any one of them. This is a multi-target attack, and it reduces effective security by log₂(number_of_targets) bits.

SPHINCS+/SLH-DSA addresses this through tweakable hash functions that incorporate public-key-specific values (the pk_seed) into every hash evaluation. This ensures that hash computations for one public key are completely independent of those for another, preventing multi-target speedups.

Randomized vs. Deterministic Signing

SLH-DSA supports both randomized and deterministic signing modes:

Randomized: Generates a fresh random value for each signature. Provides resilience against fault attacks (signing the same message twice produces different signatures, so differential fault analysis is harder). Requires a reliable random number generator
Deterministic: Derives the randomizer from the secret key and message using a PRF. Produces the same signature for the same message every time. Does not require randomness at signing time but is potentially vulnerable to fault attacks

NIST recommends randomized signing when a reliable RNG is available and deterministic signing only for environments where randomness is unreliable (e.g., deeply embedded systems).

Hash Function Agility

SLH-DSA supports both SHA-2 and SHAKE (SHA-3) based instantiations. This provides hash function agility — a critical insurance policy:

If a weakness is discovered in SHA-2, deployments can migrate to SHAKE-based parameter sets without changing the signature algorithm
If a weakness is discovered in SHA-3/SHAKE, deployments can use SHA-2-based parameter sets
Both hash function families have been scrutinized for decades with no practical attacks on full-round versions

This dual-hash-family support is unique among NIST’s standardized PQC algorithms and further reinforces the conservative posture of hash-based signatures.

Security Proofs and Tight Reductions

A significant advantage of hash-based signatures is the quality of their security proofs. The security of SLH-DSA can be tightly reduced to standard hash function properties:

EU-CMA security (existential unforgeability under chosen-message attack) reduces to the preimage resistance, second-preimage resistance, and undetectability (pseudorandomness) of the underlying hash function
The reduction is tight for WOTS+ — meaning the security bound does not degrade significantly from the hash function’s security to the signature scheme’s security
For the full SPHINCS+/SLH-DSA construction, the security proof accounts for the few-time nature of FORS, the multi-target resistance provided by tweakable hashing, and the probability of FORS instance reuse

In contrast, lattice-based signature proofs often involve lossy reductions that introduce significant gaps between the hardness of the underlying problem and the scheme’s security guarantee. Hash-based schemes avoid this: if the hash function provides n bits of security, the signature scheme provides very close to n bits of security. This is a concrete, quantifiable advantage for risk-conscious deployments.

Ongoing Research

Active research directions in hash-based signatures include:

Signature size reduction: Techniques like SPHINCS-alpha aim to reduce SLH-DSA signatures by 10-20% through optimized parameters and improved FORS constructions
Parallelized verification: The tree structure of SLH-DSA signatures is naturally parallelizable — different branches can be verified concurrently on multi-core processors
Hardware acceleration: Dedicated hash engines (common in modern SoCs) can dramatically speed up SLH-DSA operations. ARM CryptoCell, Intel SHA-NI, and RISC-V Zknh extensions all provide hardware-accelerated SHA-256
Compact certificate formats: Research into certificate compression and omission techniques to reduce the bandwidth impact of hash-based signatures in TLS
Streaming verification: Techniques to begin verifying portions of a hash-based signature before the entire signature has been received, reducing perceived latency on bandwidth-constrained links
Post-quantum certificate chains: Optimizing X.509 certificate chain formats to reduce the cumulative overhead when multiple SLH-DSA signatures appear in a single TLS handshake (e.g., Merkle Tree Certificates draft)

12. Summary: The Security-Size Spectrum

Hash-based signatures represent the conservative end of the post-quantum signature spectrum. They trade signature size for cryptographic confidence:

Security Confidence vs. Signature Size

Maximum ──────────────────────────────────────────── SLH-DSA (hash-based)
Confidence    │                                       XMSS/LMS (stateful hash)
              │                                  ML-DSA (lattice-based)
              │                             FN-DSA (structured lattice)
Minimum ──────────────────────────────────────────── Classical (RSA, ECDSA)
              │
              Small ──────────── Signature Size ──────────── Large

When to use hash-based signatures: Whenever the long-term integrity of signatures matters more than the bandwidth cost of larger signatures. Root CAs, firmware signing, code signing, archival documents, and trust anchors are the primary targets. For high-throughput, bandwidth-sensitive applications, ML-DSA is the better choice — but for the cryptographic bedrock that everything else rests on, hash-based signatures provide the strongest foundation.

For the broader context of NIST’s PQC standardization decisions, see NIST PQC Standardization Process. For lattice-based alternatives, see Lattice-Based Cryptography. For practical migration planning, see PQC Migration Strategies.

Previous: Lattice-Based Cryptography — ML-KEM and ML-DSA, the primary post-quantum standards built on lattice problems.

Next: Code-Based Cryptography — McEliece, BIKE, and HQC: post-quantum encryption from error-correcting codes.