Hash-Based Signatures

Imagine you are about to sign a document. The cryptographic scheme in your HSM needs one of several possible "hard problems" to rest on. Factoring? Shor breaks it. Elliptic-curve discrete log? Shor again. Lattices? Probably safe — but the hardness is a conjecture supported by about fifteen years of serious cryptanalysis, not sixty. Codes? Similarly. The one thing every cryptographer deeply believes will remain hard — hard even on a quantum computer, hard even if tomorrow's mathematician walks in with a new idea — is inverting a cryptographic hash function. SHA-256 and SHAKE-256 are studied by everyone who does cryptanalysis, used by every blockchain and every code-signing chain on Earth, and every attempted attack against them has so far moved the goalposts by only a few bits.

So here is the question: can you build a digital signature scheme whose security rests on nothing but the hardness of inverting a hash? You cannot use modular exponentiation, cannot use elliptic curves, cannot use lattice problems. Only hashes. This chapter answers that question. The answer is yes — and the construction was first described by Leslie Lamport and Ralph Merkle, independently, in 1979. It was ignored for forty years because RSA was smaller and faster; now that RSA is ending, hash-based signatures have returned as the conservative anchor of the post-quantum portfolio. NIST standardised one of them, SPHINCS+, as FIPS 205 (SLH-DSA) in August 2024. Your HSM vendor is adding it to the firmware right now.

The setup: one hash function, one idea

A cryptographic hash function H takes a bit-string of any length and produces a fixed-length digest — say H : \{0,1\}^* \to \{0,1\}^{256}. You need two properties:

• One-way (preimage resistance): given a digest y, finding any x with H(x) = y takes \sim 2^{256} work.
• Collision resistance: finding any pair x \ne x' with H(x) = H(x') takes \sim 2^{128} work (the birthday bound).

SHA-256 and SHAKE-256 are the standard choices. On a quantum computer, Grover's algorithm halves the preimage security to \sim 2^{128}, and the BHT algorithm drops collision-finding to \sim 2^{85}. Parameter sets account for this — SPHINCS+-128 targets classical-128/quantum-96 security, SPHINCS+-256 targets classical-256/quantum-128.

Everything below is built from hashing. No other primitive.

Lamport's one-time signature

Leslie Lamport's 1979 construction is the starting point. You can sign one message per key. The mechanics are embarrassingly simple.

Key generation (for a message of n bits; for SHA-256 take n = 256).

1. For each bit position i \in \{1, \ldots, n\}, sample two random 256-bit secrets: x_i^0 and x_i^1. That is 2n random values in total.
2. The private key is the full collection \{x_i^0, x_i^1\}_{i=1}^n.
3. The public key is the hashes: \{H(x_i^0), H(x_i^1)\}_{i=1}^n.

Signing a message m. Let m = m_1 m_2 \ldots m_n be the bits of the message (or, more commonly, of H(m) — signing the hash of the message means the scheme works for messages of any length).

For each bit position i, reveal x_i^{m_i}. The signature is \sigma = (x_1^{m_1}, x_2^{m_2}, \ldots, x_n^{m_n}) — exactly n of the 2n secrets.

Verification. For each bit i, compute H(x_i^{m_i}) (from the signature) and check that it equals the public-key entry that was supposed to correspond to bit m_i at position i. If all n checks pass, accept.

Why Lamport works: to forge a signature on a new message m', the attacker must produce x_i^{m'_i} for every bit position i. For positions where m_i = m'_i, the secret has been revealed — so no work. For positions where they differ, the attacker needs a preimage of H(x_i^{m'_i}) — exactly 2^{256} work for SHA-256, or 2^{128} with Grover. As long as m' differs in at least one bit from m, forgery requires solving at least one preimage problem.

The catch: "one-time" is literal. Sign two different messages and, at every position where the bits disagree, the attacker learns both x_i^0 and x_i^1. Across enough different messages, the entire private key leaks. You must use each Lamport key pair exactly once.

Winternitz — reducing Lamport's key size

A Lamport signature has n (256) revealed values, and the public key is 2n hashes. Winternitz (1979, published anonymously in the same Merkle paper) compressed this. Instead of revealing one of two secrets per bit, hash a single secret many times and reveal an intermediate hash whose "depth" encodes a chunk of the message. Groups of w message bits collapse to one chunk; the signature size drops by roughly a factor of w / \log_2 w, at the cost of proportionally more hashing at sign and verify time. WOTS+ (the Winternitz variant used inside SPHINCS+ at the bottom of each Merkle leaf) is a more tightly-tuned version of the same idea, with a parameter w = 16 being standard.

Merkle's trick — 2^h messages from one public key

Lamport's one-time limit looks fatal for practice. You want to sign thousands of messages from one long-lived key pair — not run a fresh ceremony per signature. Ralph Merkle's 1979 paper solved this.

Build a binary tree of Lamport public keys. Generate 2^h independent Lamport key pairs. Each key pair's public key is a list of 2n hashes; hash the whole list into a single 256-bit value \text{pk}_i for i = 0, \ldots, 2^h - 1. These 2^h hashes are the leaves of a Merkle tree.

The internal nodes are pairwise hashes. For every two siblings at the bottom, the parent node is the hash of the two children concatenated. Recurse up: parent of two internal siblings is the hash of their concatenation. At the top, a single 256-bit value — the Merkle root — is the long-lived public key.

Signing. To sign message m with leaf i:

1. Use the ith Lamport one-time key to produce a Lamport signature \sigma_i of m.
2. Emit the tuple (i, \sigma_i, \text{pk}_i, \text{auth-path}_i) where \text{auth-path}_i is the list of h sibling hashes on the way from leaf i to the root.
3. Mark leaf i as used. Never use it again.

Verifying. The verifier:

1. Recomputes the Lamport-public-key hash from \sigma_i and m and checks it equals \text{pk}_i.
2. Hashes up the tree using the authentication path: at each level, combines the current value with the supplied sibling, in the correct order. At the top, compares against the published root.

Why one root covers 2^h signatures: each Merkle-tree path is a witness that a particular Lamport public key belongs in slot i. Because the attacker cannot forge a hash collision, they cannot fake a leaf's position without inventing a new Lamport public key whose hash collides with one the signer's tree. So the public key (the root) commits the signer to all 2^h Lamport keys at once, and any valid signature traces back to one of them.

The stateful problem

Merkle trees give you 2^h signatures from one public key — but you must keep track of which leaves you have already used. That is state. And state is a nightmare in production.

• Suppose your signing key lives on two HSMs for availability. Both are primed to use leaf 42 for the next signature. Both sign. The attacker now has two different messages signed with the same one-time key — Lamport's entire private key at position 42 leaks, the attacker forges arbitrary messages.
• Suppose your HSM crashes and you restore it from a backup made five minutes ago. The backup thinks the next leaf is 42; but between backup and crash you signed leaves 42, 43, 44 and archived them. The restored HSM signs at leaf 42 again, colliding with an already-published signature. Same disaster.

XMSS and LMS are the stateful hash-based signature schemes standardised in NIST SP 800-208 (2020). They work beautifully in highly controlled environments — code-signing keys on a single air-gapped workstation, firmware roots where the signer is a single ceremony — but they come with a state-management burden so severe that the standard literally warns against using them in any setting where duplicate HSMs or rollbacks are possible.

SPHINCS+ — statelessness by construction

SPHINCS+ solves the state problem. The core idea: if there are enough leaves, pick a leaf uniformly at random — the probability of colliding with any past choice is vanishing even after a large number of signatures. No state needed, no counters, no rollbacks to worry about.

But "enough leaves" is a lot. To make the collision probability negligible over 2^{64} signatures, you want a tree with roughly 2^{64} leaves. A Merkle tree of that height is impractical to build — computing the root would require 2^{64} Lamport key generations, each hashing a few thousand bytes. SPHINCS+ handles this by virtualising the tree.

The hypertree. Instead of one height-64 Merkle tree, SPHINCS+ stacks several smaller Merkle trees — say twelve layers of height 5 each, giving 2^{60} effective leaves. Each layer's "leaf" is actually the root of another Merkle tree (a WOTS+ one-time signature tree), and each root is signed by a Merkle signature at the layer above. Only the top-layer root of the topmost tree is the public key; the rest of the hypertree is generated on-demand from a seed.

The FORS few-time signature at the bottom. The very bottom layer does not use a WOTS+ one-time signature — it uses a FORS (Forest of Random Subsets) scheme, which is a few-times signature tolerant to more than one signing at the same FORS instance. This lets SPHINCS+ handle the birthday-style risk that random leaf selection will pick the same bottom-tree twice: the FORS at that instance can absorb a few re-uses without leaking the key.

How a signature is produced.

1. Derive a pseudorandom leaf index from H(m, r) where r is a per-signature randomiser.
2. At the bottom layer, at that leaf, produce a FORS signature of H(m).
3. The FORS public key at that leaf is the value you need to authenticate up the tree. Produce a WOTS+ signature of it at the layer above (this consumes the WOTS+ one-time key at the appropriate position).
4. Produce a Merkle authentication path from that WOTS+ position to the Merkle root of its layer.
5. Repeat steps 3–4 for each of the d layers. The final authentication path ends at the top root — which is the public key.

The signature is the concatenation of all these pieces. Verification reverses the process: check the FORS signature, climb upward through the hypertree, and confirm the final root matches the public key.

How "stateless" is this, really? The per-signature randomiser r is chosen freshly (per signature) and mixed into the leaf-index derivation. The probability that two signatures use the same bottom-leaf FORS instance in the same problematic way is exponentially small — small enough that you can sign 2^{64} messages under one key with negligible total failure probability. In practice you will never come close to that limit.

Parameter sets and sizes

SPHINCS+ (FIPS 205 SLH-DSA) is parameterised in two dimensions: security level and small-vs-fast (trades signature size for signing speed).

Timings on a modern x86 core; much slower on embedded hardware.

Two observations are worth sitting with. First, the public key is tiny: 32–64 bytes, smaller than any other PQC scheme. Second, the signature is enormous: kilobytes at minimum, tens of kilobytes at worst. SPHINCS+ is brilliant for any use case where public keys must be distributed widely (firmware verification, certificate transparency logs) but signatures are rare; it is a poor fit for high-throughput signing.

Worked example — a Lamport one-time signature end to end

Worked example — a height-3 Merkle signature

When to pick SPHINCS+ over Dilithium

SPHINCS+ is expensive. You pay in bytes (signatures 3–15× larger than Dilithium's) and in time (signing 10–100× slower). What you get is a security argument that depends on nothing but the hash function. Three situations where that is worth the cost:

Government long-lived signatures. A defence memo signed today must be verifiable in 2075. If Dilithium's lattice assumption is quietly broken in 2045, every Dilithium-signed document from 2026 becomes forge-able retroactively. SPHINCS+'s security depends only on the hash — and if SHA-256 falls, so does every other cryptographic system on Earth at the same moment. Correlated failure is tolerable; independent failure is not.

Certificate root of trust. The CCA (Controller of Certifying Authorities) root certificate in India is the anchor under which all DigiLocker, Income Tax, and e-Court signatures chain. The root is re-issued every 20 years; it signs a handful of intermediate CAs; verification happens billions of times. A SPHINCS+ signature at the root — big, slow, but cryptographically conservative — is exactly the right choice.

Firmware code-signing. A router firmware image is signed once and verified by millions of devices over a decade. The signer is a single HSM at the vendor's secure facility; the verifier is a small embedded chip. Signing cost (100 ms) is negligible amortised over the release; signature size (8 kB) is negligible next to the firmware image itself (100 MB); cryptographic conservatism matters because you cannot easily re-sign a decade of deployed firmware if an assumption breaks.

Where not to use SPHINCS+. Anywhere high-throughput signing matters. UPI transactions, TLS certificates, IoT telemetry — the signing cost and signature size eat the latency and bandwidth budget. Use Dilithium or Falcon here; keep SPHINCS+ for the slow, rare, deeply-trusted signatures.

Indian deployment context

CERT-In's draft 2026 PQC transition guideline calls out SPHINCS+ specifically for:

• The CCA root-of-trust ceremony from 2028 onwards (alongside Dilithium for intermediate CAs).
• DigiLocker long-lived document signatures (birth certificates, marksheets, property deeds) where the 20+ year secrecy horizon justifies the conservative choice.
• Ministry of Defence and Ministry of External Affairs archival communications, where the 50–75 year horizon makes any single-assumption crypto unacceptable.
• Code signing for government firmware (defence systems, ISRO satellite payloads, CDAC-supplied HSMs).

IIT Kharagpur's SETS lab (Mukhopadhyay group) has contributed side-channel-resistant FORS and WOTS+ hardware implementations to the open CRYSTALS/SPHINCS+ reference codebase. IIT Madras and IISc have published formal verification passes on the SHAKE-based SPHINCS+ parameter sets. CDAC's HSM product line is scheduled to ship SLH-DSA support in its 2027 firmware refresh, positioned as the "conservative" signature option alongside ML-DSA (Dilithium) as the default.

Common confusions

• "Hash-based signatures are weaker because they're simpler." The opposite is true. The fewer the assumptions, the stronger the security argument. SPHINCS+ depends only on SHA-256's second-preimage resistance — a property directly tested by every cryptanalyst every day. Dilithium depends on SHA-256 and Module-LWE's conjectured quantum hardness. If either falls, Dilithium falls; SPHINCS+ only falls if SHA-256 does.
• "SPHINCS+ is a hash function." No. SPHINCS+ is a signature scheme that uses a hash function (SHA-256 or SHAKE) as its only cryptographic primitive. The confusion is sometimes made because the name sounds like a hash. Under the hood, every operation — key generation, signing, verification — is a sequence of hash calls on specific inputs.
• "All hash-based signatures are stateless." No. XMSS and LMS (NIST SP 800-208) are stateful: the signer must track which one-time key was last used, and getting the state wrong leaks the private key. SPHINCS+ is the only NIST-standardised stateless hash-based signature; statelessness is a design goal, purchased with larger signatures and a more elaborate tree structure.
• "Merkle trees prove blockchain works, not that signatures work." Merkle trees appear in both. In a blockchain, they prove transaction inclusion without revealing other transactions. In SPHINCS+, they prove leaf-key inclusion without revealing other keys. Same data structure, different cryptographic role — and the 1979 paper that introduced the idea was the signature paper; blockchain adopted the technique decades later.
• "SPHINCS+ is new and unproven." SPHINCS+ the name dates from 2015, but every building block is older. Lamport 1979, Merkle 1979, WOTS+ 2011, FORS 2017. SHA-256 has been under continuous cryptanalysis for over two decades. The composition was standardised by NIST in 2024 after four rounds of open cryptanalysis. "Conservative" is the accurate description, not "new."
• "Bigger signatures are a small price to pay." Depends on the use case. A 10× signature-size increase for a UPI payment switch carrying 500 transactions per second is a 10× backhaul cost — meaningful. A 10× increase for a firmware root-of-trust signed twice a year is nothing. The style guide for post-quantum migration is to match the algorithm to the deployment, not to pick one winner for all jobs.

Going deeper

Winternitz one-time signatures (WOTS+)

WOTS+ compresses Lamport. Fix a parameter w (typically 16). Encode the message H(m) in base w as \ell_1 digits, plus a small number of checksum digits to prevent truncation attacks. For each digit, the private key holds one random 256-bit secret x_j, and the public key holds its w-th iterated hash H^{w-1}(x_j).

To sign a digit d_j, release H^{d_j}(x_j) — the secret hashed d_j times. The verifier then hashes w - 1 - d_j more times and checks the result equals the public-key entry.

Why the checksum matters: without it, the attacker could take a signature on digit value d and use it as a signature on any larger value d' > d by simply hashing d' - d more times. The checksum, added at the end of the message encoding, is the complementary sum \sum (w - 1 - d_j) — it decreases as the message digits increase, preventing the attacker from truncating a signature into a forgery.

WOTS+'s signature for a 256-bit message is \ell = \ell_1 + \ell_2 values of 256 bits each — for w = 16 that is \ell \approx 67, about a quarter of Lamport's n = 256. Hence smaller signatures at the cost of a w-factor in hashing work.

XMSS tree hashing and its stateful shadow

XMSS (Extended Merkle Signature Scheme) is Merkle-tree-of-WOTS+. The tree has 2^h leaves, each a WOTS+ public key. The signer keeps a counter i and signs the i-th message with the i-th leaf, then increments. To avoid leaking the private key through reuse, the counter must be durably stored and atomically incremented before each signing.

The operational nightmare. If the HSM has a master-slave replica for availability, both replicas must share the counter — but atomic cross-HSM coordination is expensive and fragile. If the HSM is restored from a backup, the backup's counter is behind; the first signing after restore reuses a leaf. Airbus has published incident reports on exactly this failure mode. NIST SP 800-208 permits XMSS and LMS but essentially prohibits them in any setting where state could be rolled back or replicated — a very narrow permission.

LMS — Leighton-Micali Signatures

LMS is a parallel stateful construction to XMSS, with slightly different parameter choices and a somewhat simpler WOTS+ variant. Both XMSS and LMS are NIST-approved; the IETF RFC 8391 (XMSS) and RFC 8554 (LMS) specify the formats. For code-signing use cases with a strictly single-HSM signer (no replication, no rollback), LMS is common — it was the signature used for the 2019 Linux Foundation secure boot-chain proof-of-concept.

SPHINCS+ parameter derivation

SPHINCS+'s core parameters:

• n: hash output length (128, 192, or 256 bits, matching security level).
• h: total hypertree height (63–68 depending on parameter set).
• d: number of layers (7–22).
• h' = h / d: Merkle-tree height per layer.
• w: Winternitz parameter (16 in all standardised parameters).
• k, t, a: FORS parameters (number of trees per FORS instance, tree-leaf count, addressed bits per tree).

The "s" (small) and "f" (fast) variants differ in h/d/\log_2 t: "s" takes fewer larger trees, so each FORS instance is expensive but few are touched per signature; "f" takes more smaller trees, so signing is faster but signatures are bigger.

Security proofs

In the quantum random-oracle model (where the adversary can query the hash function in superposition), SPHINCS+'s existential unforgeability reduces to:

1. The preimage resistance of H (protects WOTS+ chains).
2. The collision resistance of H (protects Merkle tree authentication).
3. The second-preimage resistance of H (protects FORS few-time signatures).

All three are standard hash-function assumptions. No other assumption is made. The concrete reduction loses a small polynomial factor in the security parameter — meaning 128-bit-security SPHINCS+ gives ~125 bits of quantum security in the worst case.

Stateful hash-based signatures in India's public sector

NIST SP 800-208 explicitly permits stateful hash-based signatures for use cases with a single dedicated signer and no replication:

• Satellite firmware signing (ISRO): a single signing ceremony per release, long verification life, no replication.
• Root-of-trust boot keys (CDAC HSMs): one master signer, forever-rooted devices.
• e-ID provisioning keys (UIDAI pilot): stateful XMSS in a carefully-controlled HSM environment, considered but not deployed.

CERT-In's 2026 draft steers general deployments toward SPHINCS+ precisely because the state-management burden is unmanageable in a typical enterprise. The exception is listed for narrowly defined high-assurance ceremonies.

Where this leads next

• Lattice-Based Cryptography — the faster, smaller family of post-quantum signatures (Dilithium, Falcon) whose security rests on Module-LWE hardness.
• Code-Based and Isogeny-Based Cryptography — the other NIST candidates: Classic McEliece, HQC, and why SIKE collapsed in 2022.
• Post-Quantum Cryptography: Why Now — the harvest-now-decrypt-later argument and India's National Quantum Mission migration roadmap.
• Quantum Crypto Threat Model — which primitives Shor and Grover actually threaten, and how hard each replacement has to be.
• Factoring and RSA — the structural weakness at the heart of the signatures SPHINCS+ is retiring.

References

1. Ralph Merkle, A Certified Digital Signature (CRYPTO '89, with the 1979 construction revived) — merkle.com/papers/Certified1979.pdf.
2. NIST, FIPS 205 — Stateless Hash-Based Digital Signature Standard (SLH-DSA) — csrc.nist.gov/pubs/fips/205.
3. NIST, SP 800-208 — Recommendation for Stateful Hash-Based Signature Schemes (XMSS, LMS) — csrc.nist.gov/pubs/sp/800/208/final.
4. Wikipedia, Lamport signature.
5. Wikipedia, Hash-based cryptography.
6. John Preskill, Lecture Notes on Quantum Computation, Chapter 8 (Cryptography) — theory.caltech.edu/~preskill/ph229.