Hash-Based Cryptography
Hash-based cryptography is a family of post-quantum signatures whose security rests only on the strength of a hash function, with no reliance on the algebraic hard problems (factoring, discrete logarithms) that a quantum computer breaks. Because a good hash function is the best-understood and most heavily attacked primitive in all of cryptography, this family carries the strongest long-term confidence of any post-quantum option. The two standardized branches are the stateful schemes XMSS and LMS and the stateless SLH-DSA (the standardized form of SPHINCS+). The one cost you pay for that confidence is size: hash-based signatures are large.
The short version:
- Hash-based cryptography does signatures only. There’s no hash-based key-establishment mechanism, so ML-KEM still handles the confidentiality side of the transition.
- Its security depends on one assumption: that the underlying hash function stays collision- and preimage-resistant. That’s the most conservative bet in cryptography, which makes this family the ultimate hedge.
- It comes in two forms. Stateful (XMSS, LMS) is extremely compact but you must track every key you’ve used. Stateless (SLH-DSA) removes that burden at the cost of much larger signatures.
- The stateful footgun is real: signing two different messages with the same one-time key breaks the scheme, which is why XMSS and LMS live inside HSMs and secure hardware that can guarantee a key is never reused.
- It’s the go-to for firmware signing, roots of trust, and long-lived signatures, exactly the places where you want maximum confidence and can absorb a large signature.
Picture a booklet of single-use wax stamps, where each stamp can be pressed exactly once to seal exactly one message, and pressing the same stamp twice reveals enough to forge it. That’s a one-time signature, and you can build one out of nothing but a hash function. The problem is you’d need a fresh stamp for every message, and no one wants to publish thousands of separate public keys. So you take the fingerprints of a whole stack of these one-time keys and combine them, pair by pair, into a single master fingerprint using a hash function. That master fingerprint (a Merkle tree root) becomes one small public key that vouches for the entire stack. When you sign, you hand over one one-time signature plus a short proof that its stamp really belongs under that published root. Every piece of that construction is a hash, which is the whole point.
How does hash-based cryptography work?
Hash-based signatures are built in two layers. The bottom layer is a one-time signature (OTS) scheme, a way to sign a single message using only hash operations, where the private key is a set of secret random values and the public key is their hashes. Signing reveals a specific subset of those secrets chosen by the message digest, and a verifier re-hashes them to check the match. The catch is in the name: an OTS key is safe for exactly one message, because a second signature under the same key leaks enough structure to forge new ones.
The top layer solves the “one key per message” problem with a Merkle tree (a hash tree). Many one-time public keys are hashed together, pair by pair, up to a single root value that serves as the long-term public key. A signature then carries three things: the one-time signature itself, the one-time public key that produced it, and the short authentication path of sibling hashes needed to recompute the root. If the recomputed root matches the published one, the signature is valid. Security reduces cleanly to the hash function’s collision-resistance and preimage-resistance, with no number-theoretic structure anywhere in the construction.
Source: NIST SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes, October 2020; NIST FIPS 205, Stateless Hash-Based Digital Signature Standard, August 2024.
There’s no hash-based KEM. Hash functions don’t naturally support key encapsulation, so this family only ever produces signatures. Post-quantum key establishment comes from ML-KEM instead.
Why is it the most conservative post-quantum family?
Hash-based cryptography is the most conservative post-quantum family because it rests on the single best-understood assumption in the field. Every other post-quantum family stakes its security on a hard problem we’re still building long-term confidence in: lattice problems behind ML-KEM and ML-DSA, the coding-theory problems behind code-based schemes, isogeny problems, multivariate systems. Those are promising and heavily studied, but they’re younger, and they carry algebraic structure that future cryptanalysis could exploit.
A hash function has none of that structure to attack. It’s been the workhorse of the field for decades, it’s been hammered on relentlessly, and its security properties are about as well-mapped as anything in cryptography gets. Shor’s algorithm, the quantum attack that dismantles RSA and elliptic-curve cryptography, needs exactly the algebraic structure that hash functions lack, so it simply doesn’t apply here. The one quantum lever is Grover’s algorithm, which gives a quadratic speedup on searching for a hash preimage and effectively halves a hash function’s security margin. The schemes handle that by sizing their hash outputs to absorb it: SLH-DSA builds on SHA-2 and SHA-3 with output sizes chosen so the Grover discount still leaves a comfortable margin.
Source: NIST FIPS 205, August 2024.
That’s the trade at the heart of the family. You give up compact signatures and, in the stateful case, take on a management burden, and in return you get the strongest confidence any post-quantum family can offer that your signatures will still hold decades from now.
Stateful vs stateless: what’s the difference?
The difference is whether the signer has to remember which one-time keys it has already used. Stateful schemes track that state and stay compact; stateless schemes design the state away and pay for it in signature size. Both are current standards for different jobs, not old-and-new versions of the same thing.
Stateful (XMSS and LMS). These maintain a counter of used one-time keys and must guarantee each key signs at most once. That makes them remarkably compact and efficient, but it puts a hard operational requirement on the signer: reusing a one-time key is catastrophic and breaks the scheme’s security. In practice that means XMSS and LMS live inside HSMs or secure hardware that can track state reliably, and they suit low-volume, high-assurance signing rather than high-throughput services. They’re standardized in NIST SP 800-208 and in RFC 8391 (XMSS) and RFC 8554 (LMS).
Stateless (SLH-DSA / SPHINCS+). SLH-DSA removes the state requirement entirely by randomizing which one-time keys get used, so there’s no counter to maintain and no reuse footgun. That makes it safe to deploy anywhere, including ordinary software with no special hardware. The price is signature size: SLH-DSA signatures run from 7,856 bytes for the smallest parameter set up to 49,856 bytes for the largest, while its public keys stay tiny at 32 to 64 bytes.
Source: NIST FIPS 205, Table 2, August 2024.
| Stateful (XMSS, LMS) | Stateless (SLH-DSA / SPHINCS+) | |
|---|---|---|
| State required | Yes; must track every used one-time key | None |
| Key-reuse risk | Reusing a one-time key breaks security | None |
| Signature size | Compact | Large: 7,856–49,856 bytes (FIPS 205 Table 2) |
| Standard | NIST SP 800-208; RFC 8391 (XMSS), RFC 8554 (LMS) | FIPS 205 |
| Best fit | HSM-backed signing where state is managed reliably | Broad deployment where large signatures are acceptable |
Where does it fit best?
Hash-based signatures fit best where you want maximum long-term confidence and can absorb a large signature: firmware and boot signing, roots of trust, code signing, and long-lived offline signatures like certificates for durable trust anchors. In all of those, a signature might need to verify years or decades after it’s made, signing happens infrequently enough that size and throughput aren’t the bottleneck, and the conservative security model is worth the tradeoff.
That’s why NSA CNSA 2.0 singles out the stateful schemes, LMS and XMSS, specifically for software and firmware signing rather than for general-purpose use.
Source: NSA CNSA 2.0, Announcing the Commercial National Security Algorithm Suite 2.0, September 2022.
Where an organization wants the stateless option so it doesn’t have to manage a counter, SLH-DSA fills the same conservative-anchor role without the state burden.
Two boundaries matter. For high-volume, size-sensitive signing traffic, ML-DSA is the smaller, faster default, so hash-based signatures earn their place at the durable, low-frequency end instead. And key establishment stays the job of ML-KEM.
Common misconceptions
“Hash-based crypto can also do encryption or key exchange.” It signs, and only signs. There’s no hash-based KEM, so confidentiality and key establishment stay with ML-KEM. Treating this family as a full drop-in replacement for everything a quantum computer breaks misses that the transition has a separate signature side and key-establishment side.
“Stateless SLH-DSA just replaces stateful XMSS and LMS.” Both are current NIST-backed standards aimed at different jobs. Stateful schemes stay in the toolkit precisely because they’re far more compact, which is exactly what firmware signing wants when the signer can manage state safely. Stateless SLH-DSA trades that compactness for freedom from state management.
“Grover’s algorithm breaks hash-based signatures.” Grover delivers a quadratic speedup on preimage search, which effectively halves a hash function’s security margin, and the schemes are designed to absorb it by choosing hash output sizes accordingly. That’s a manageable discount, a different situation entirely from the way Shor’s algorithm fully dismantles RSA and elliptic-curve cryptography.
“The large signatures make it impractical.” The size is the price of the most conservative security assumption available, and for trust roots and firmware, where a signature is written once and trusted for years, that trade is usually worth making. The size only becomes a real problem in high-volume, bandwidth-sensitive contexts, and those are the ones better served by ML-DSA anyway.
Hash-based cryptography is the conservative anchor of the post-quantum toolkit: the family you reach for when a signature has to be trusted for a very long time and you want the strongest possible confidence it’ll still hold. Everything here is the map, given freely. When your team needs to decide where SLH-DSA, XMSS, and LMS actually belong across your firmware, roots of trust, and signing estate, that’s what an alignment briefing is for.
Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.