What is a Lamport one-time signature?

A Lamport one-time signature is the foundational hash-based primitive. To sign an n-bit message digest, the signer generates 2n random secret values and publishes their hashes as the public key, then signs by revealing the secret value corresponding to each message bit. It is secure but strictly one-time, because signing two different messages with the same key exposes enough secret values to allow forgery.

What are Merkle trees used for in hash-based signatures?

A Merkle tree lets a single public key authenticate many one-time signature keys, solving the impracticality of using one-time keys alone. Each leaf is the hash of one one-time public key, every internal node is the hash of its two children, and the root becomes the long-term public key. To sign, the signer includes an authentication path of sibling hashes that lets a verifier recompute and check the root.

What is the difference between stateful and stateless hash-based signatures?

Stateful schemes like XMSS and LMS require the signer to record which one-time keys have been used and never reuse a leaf, because reuse collapses security; they produce smaller, faster signatures but demand rigorous state management. Stateless schemes like SPHINCS+ remove that burden by selecting a leaf pseudorandomly from a huge virtual tree, making harmful reuse negligible without tracking state, at the cost of larger signatures and slower signing.

What are SPHINCS+ and SLH-DSA?

SPHINCS+ is a stateless hash-based signature scheme standardized by NIST as SLH-DSA in FIPS 205. It builds a huge virtual hypertree and selects a leaf pseudorandomly based on the message and a secret, so no state tracking is needed, and it uses a few-time signature at the leaves to absorb the small chance the same leaf is chosen twice. It serves as a conservative backup within the post-quantum signature portfolio.

Why is reusing a key catastrophic in stateful hash-based signatures?

Stateful schemes such as XMSS and LMS build on one-time signatures, which leak secret material if the same leaf signs two different messages, enabling forgery. Reuse can happen accidentally, for example after restoring a virtual machine from a snapshot or cloning a key, so the signer must carefully track and never repeat leaf usage. This is why stateful schemes are best suited to controlled environments such as firmware signing.

⚛ Quantum & Post-Quantum

Hash-Based Signatures: SPHINCS+, XMSS, and Lamport

Hash-based signatures are digital signature schemes whose security depends only on the properties of a cryptographic hash function, rather than on number-theoretic problems like factoring or discrete logarithms. This makes them among the most conservative quantum-resistant signatures available, because a secure hash function is a very well understood assumption and Grover's algorithm only mildly weakens it. This article traces the construction from Lamport one-time signatures through Merkle trees to the standardized XMSS and stateless SPHINCS+ (SLH-DSA) schemes.

Security From Hash Functions Alone

Every scheme here reduces forgery to breaking a hash function's preimage or collision resistance. Since Shor's algorithm does not help against hash functions and Grover's algorithm offers only a quadratic speedup, using a hash with a sufficiently large output (256 bits or more) preserves strong security against quantum adversaries. The trade-off is that hash-based signatures are larger and, in some variants, require the signer to track state.

Lamport One-Time Signatures

The foundational primitive is the Lamport one-time signature (OTS). To sign an n-bit message digest, the signer generates 2n random secret values and publishes their hashes as the public key.

# Lamport OTS for an n-bit message digest
secret key:  sk[i][b]  for i in 0..n-1, b in {0,1}   # 2n random values
public key:  pk[i][b] = H(sk[i][b])                  # hash each one
sign(m):     for each bit i of m, reveal sk[i][ m_i ]
verify:      check H(revealed) == pk[i][ m_i ] for all i

Verification hashes each revealed value and compares it to the public key. The scheme is secure but strictly one-time: signing two different messages with the same key exposes enough secret values to allow forgery, and keys and signatures are large.

Winternitz One-Time Signatures

The Winternitz OTS (WOTS) shrinks Lamport signatures by trading space for computation. Instead of one secret per bit, it processes several message bits at a time as a small integer and signs by hashing a secret value that many times in a chain. Verifiers continue the chain to reach the public value. Increasing the Winternitz parameter yields shorter signatures at the cost of more hashing, and WOTS+ is the variant used inside modern schemes.

Merkle Trees and the Merkle Signature Scheme

One-time keys are impractical alone, so Ralph Merkle's insight was to authenticate many of them with a single public key using a Merkle tree (hash tree). Each leaf is the hash of one OTS public key, and every internal node is the hash of its two children. The root becomes the long-term public key.

To sign the i-th message, the signer uses the i-th OTS key and includes an authentication path, the sibling hashes needed to recompute the root. Verifiers hash up the path and check that it reproduces the trusted root. A tree of height h authenticates 2ʰ one-time keys under one compact public key.

Stateful Schemes: XMSS and LMS

XMSS (eXtended Merkle Signature Scheme) and LMS (Leighton-Micali Signatures) are standardized, practical Merkle-tree schemes. Both are stateful: the signer must record which one-time keys have been used and never reuse a leaf. XMSS strengthens the classic design with WOTS+, bitmasked hashing for tighter security proofs, and hypertrees that layer multiple Merkle trees so key generation does not have to build one enormous tree up front.

The critical operational hazard is state management. If a signer reuses a leaf, perhaps after restoring a virtual machine from a snapshot or cloning a key, security collapses. This makes stateful schemes best suited to controlled environments such as firmware signing, where key use is carefully sequenced.

Stateless Signatures: SPHINCS+ (SLH-DSA)

SPHINCS+, standardized as SLH-DSA in FIPS 205, removes the state-tracking burden. It builds a huge virtual hypertree, far too large to compute in full, and selects a leaf pseudorandomly based on the message and a secret. The chance of harmful reuse becomes negligible without tracking state. To keep each signature to one use safely, the leaves sign with a few-time signature (FORS) rather than a one-time scheme, absorbing the small probability that the same leaf is chosen twice. The result is a completely stateless signature at the cost of larger signatures and more hashing per operation.

Stateful Versus Stateless Trade-offs

XMSS and LMS produce smaller signatures and are faster, but demand rigorous state management and a bounded number of signatures per key.
SLH-DSA (SPHINCS+) is stateless and operationally robust, but its signatures are considerably larger and signing is slower.
All variants offer conservative, well-studied security, which is why hash-based signatures serve as a trusted backup within the broader post-quantum portfolio.

Key Takeaways

Hash-based signatures rely only on hash-function security, making them a conservative quantum-resistant choice.
Lamport OTS signs by revealing preimages; Winternitz compresses this by hashing in chains.
Merkle trees authenticate many one-time keys under a single root public key via authentication paths.
XMSS and LMS are efficient but stateful, so reusing a one-time key is catastrophic and must be prevented.
SPHINCS+ (SLH-DSA) is stateless through pseudorandom leaf selection and few-time signatures, trading larger signatures for operational safety.

hash-based-signaturessphincs-plusxmsslamportmerkle-trees