Hash-based signatures

Hash-based signatures are digital signature schemes whose security rests entirely on the properties of cryptographic hash functions rather than on number-theoretic or structured algebraic assumptions. They are the most conservative post-quantum signature family: standardized as the stateful schemes XMSS and LMS and the stateless SLH-DSA, they trade large signatures and slower signing for minimal, well-understood security assumptions.

#From one-time signatures to Merkle trees

The construction is built from pieces dating to the late 1970s. A Lamport one-time signature signs a single message by revealing preimages of published hash values; signing two different messages with the same key leaks enough material for forgery. Winternitz variants (WOTS+) compress the idea by hashing in chains. Ralph Merkle's contribution was the Merkle tree: authenticate many one-time public keys under a single root hash, so one small public key can validate thousands of one-time signatures. Every modern hash-based scheme is an elaboration of this tree design, and its security reduces to standard hash function properties (preimage, second-preimage, and related resistance) that Grover's algorithm dents only quadratically.

#Stateful schemes: XMSS and LMS

XMSS (RFC 8391, 2018) and LMS (RFC 8554, 2019) are direct Merkle-tree schemes. NIST approved both for US government use in SP 800-208 (2020). They are efficient: public keys of tens of bytes, signatures of roughly 1 to 3 kilobytes, and fast verification.

Their defining hazard is state. Each one-time key in the tree may be used exactly once, so the signer must durably record which leaf indexes have been consumed. Restoring a signer from a backup, cloning it into a virtual machine snapshot, or replicating it for high availability can silently reuse a leaf and destroy all security. SP 800-208 therefore restricts these schemes to hardware-bound, carefully managed signing environments, and they are not suitable as general-purpose signatures.

#Stateless: SPHINCS+ and SLH-DSA

SPHINCS+ removed the state problem (sphincs.org). It layers a hypertree of one-time signatures over a few-time signature scheme (FORS) and selects leaves pseudorandomly, making accidental reuse a matter of negligible probability instead of operational discipline. Any number of signatures can be produced with no bookkeeping. NIST standardized it as SLH-DSA in FIPS 205 on August 13, 2024; the standard is covered in detail under SLH-DSA.

Statelessness is paid for in size and speed:

For comparison, ML-DSA-65 signatures are 3309 bytes and signing is orders of magnitude faster.

#The conservative security story

The appeal of the family is what it does not assume. Breaking a hash-based signature requires breaking the underlying hash function itself; there is no lattice structure, no algebraic trapdoor, no new mathematical assumption introduced since the 1970s. If SHA-2 or SHAKE fails, all of cryptography has a crisis; short of that, hash-based signatures stand. This is why NIST standardized SLH-DSA alongside the lattice-based ML-DSA in the standardization process: it is the hedge that survives even a collapse of lattice-based cryptography. The cost side of the ledger is equally plain: signatures of 8 to 50 kilobytes and slow signing exclude it from handshake-heavy protocols like TLS.

#Where they are used

The natural home is code and firmware signing: signatures are verified often but produced rarely, in controlled facilities, and the verifying devices live for decades. NIST SP 800-208 approved LMS and XMSS specifically with this profile in mind, and the NSA's CNSA 2.0 suite lists LMS and XMSS as its approved signatures for firmware and software signing (NSA CNSA 2.0). Secure boot chains, hardware security modules, and long-lived root keys in PKI planning are the other common deployments, with SLH-DSA increasingly chosen where state management is impractical.