Hash-based signatures are the most conservative quantum-resistant signature family. Their security rests only on hash function properties, which makes them simple to analyze. But that simplicity comes with sharp trade-offs: stateful versus stateless, big signatures versus fast operations, tree height that limits signature counts, and state management hazards that can destroy security with a single misstep. Anyone deploying hash-based signatures in production needs to understand these trade-offs before signing the first message.
This post walks through the four main trade-offs hash-based signature schemes face, why each design choice matters, and how QNSQY's tier system reflects these decisions.
Trade-off 1: Stateful vs Stateless
The first and biggest trade-off in hash-based signatures is whether the scheme is stateful or stateless.
Stateful schemes like LMS and XMSS track which one-time keys have been used. Each signature uses one key, then the index advances. Reusing a key compromises the entire scheme.
Stateless schemes like SLH-DSA (FIPS 205) avoid state by hashing the message to deterministically pick which one-time keys to use. No state to track, no reuse hazard. The cost is much larger signatures.
Numbers at NIST Level 1:
LMS L=H20/W=8 signature: about 2.8 KB. State management required. SLH-DSA-128s signature: about 7.8 KB. No state required. SLH-DSA-128f signature: about 17 KB. No state required, faster signing.
The stateful schemes are smaller because they only need one Merkle path per signature. The stateless schemes need to authenticate many one-time keys per signature, blowing up the signature size.
A useful analogy: stateful is like a checkbook where you track the next check number. Lose the checkbook and you might write a duplicate check, voiding both. Stateless is like a money order where you don't track anything, but each money order is much larger and more expensive to issue.
For most users, stateless is operationally easier. For users who can manage state safely, stateful gives much smaller signatures.
QNSQY's Business tier supports both LMS (stateful, small) and SLH-DSA (stateless, larger), letting users pick based on their operational profile.
Trade-off 2: Tree Height vs Signature Count
In any tree-based signature scheme, the tree height h limits the total number of signatures to 2^h. This is a hard limit. After 2^h messages, the key is exhausted.
Trade-offs by height (XMSS or LMS at typical parameters):
h equals 10: 1,024 signatures. Key generation: 0.03 seconds. Tree size in memory: 33 KB. h equals 16: 65,536 signatures. Key generation: 1.5 seconds. Tree size: 2 MB. h equals 20: 1,048,576 signatures. Key generation: 30 seconds. Tree size: 33 MB. h equals 25: 33 million signatures. Key generation: 16 minutes. Tree size: 1 GB.
Higher trees support more signatures but cost more to generate and need more memory. For most code-signing use cases, h equals 20 is sufficient (1 million signatures over the key lifetime).
For very long signature lifetimes (above 1 million signatures), use multi-tree variants like XMSS-MT or HSS, which chain trees and support up to 2^60 signatures with reasonable per-tree sizes.
A picture: tree height is like the size of a key ring. A small ring holds few keys. A large ring holds many but is heavy and takes longer to assemble. After all keys are used, you need a new ring (a new long-term key pair).
QNSQY's LMS implementation uses h equals 20 by default, supporting 1 million signatures per key.
Trade-off 3: Winternitz Parameter w vs Speed
The Winternitz parameter w controls the trade-off between signature size and computational cost.
In a Winternitz one-time signature, each chunk of w message bits is signed by walking a hash chain to a specific position. Larger w means fewer chunks to sign (smaller signature) but deeper hash chains (more computation).
Numbers for LMS at h equals 20:
w equals 1: signature 16 KB, sign 0.5 ms, verify 0.5 ms. w equals 2: signature 8 KB, sign 1 ms, verify 1 ms. w equals 4: signature 4 KB, sign 2 ms, verify 2 ms. w equals 8: signature 2.8 KB, sign 5 ms, verify 5 ms.
The default in production is w equals 8, which gives small signatures at modest computational cost. For very fast signing (high frequency code signing or low-power devices), w equals 4 or w equals 2 may be preferred.
XMSS uses similar Winternitz parameters with similar trade-offs.
A useful analogy: w is like the number of digits per character in a numeric code. A 4-digit code per character lets you encode a lot per character but takes longer to compute. A 1-digit code is faster per character but you need many more characters.
Trade-off 4: State Management Hazards
Stateful schemes have a sharp operational hazard: state corruption or reuse destroys the scheme.
Common ways state goes wrong:
Backup restoration. Restore from a backup taken before the most recent signatures and you risk reusing indices. The backup must include the post-signature state, which means backups must run after every batch of signatures.
Multi-machine deployment. Run the signing service on two machines without coordination and both may use the same indices. Only single-machine signing is safe by default; multi-machine requires careful coordination protocols.
Process crashes. The signer must commit the new state to disk before releasing the signature. If the process crashes between releasing the signature and committing state, recovery is undefined. Robust implementations use fsync and atomic file writes to handle this.
Out-of-memory kills. The Linux OOM killer can interrupt a signing operation at any point. Same as process crashes: requires atomic state commits.
Filesystem corruption. Disk failures can corrupt state files. Robust implementations keep multiple copies and validate before use.
Reservation schemes. Some implementations allocate batches of indices upfront and consume them gradually. This reduces the per-signature state write overhead but increases the impact of state loss (lose state and you skip a whole batch).
For comparison, stateless schemes like SLH-DSA have none of these hazards. The signer can crash, restart, run on multiple machines, and never reuse a one-time key. The trade-off is signature size.
QNSQY's LMS implementation handles state management automatically with robust file commits. The user can focus on signing, not on operational details.
Trade-off 5: Hash Function Choice
Both stateful and stateless hash-based schemes depend on hash function security. Choosing the right hash function trades off security level against speed and key sizes.
NIST SP 800-208 specifies LMS and XMSS with SHA-256 or SHAKE256. FIPS 205 specifies SLH-DSA with SHAKE256 or SHA-256.
Trade-offs:
SHA-256: 128 bits of post-quantum collision resistance (256 bit output, halved by Grover). Hardware support widely available. Fast in software.
SHA-512: 256 bits of post-quantum collision resistance. Slower in software than SHA-256 unless you have 64-bit hardware. Not commonly used in hash-based signatures.
SHAKE256: 128 to 256 bits depending on output size. Modern design with stronger margins. Slightly slower than SHA-256 in software.
For NIST Level 5 signatures (256-bit security against quantum attack), SHAKE256 is the modern choice. For Level 1 to 3, SHA-256 is sufficient and faster.
Hash-based schemes are unique in that the entire security analysis reduces to hash function properties. Choosing a strong hash function is the only security knob.
Trade-off 6: Key Generation Time
Hash-based signatures have slow key generation compared to lattice signatures. Building the Merkle tree requires hashing every leaf, which takes proportional to 2^h time.
For h equals 20 with SHA-256:
Tree size: 1 million leaves Hash operations: about 2 million Time on a modern CPU: about 30 seconds
For h equals 25:
Hash operations: about 64 million Time: about 16 minutes
This contrasts sharply with ML-DSA, which generates a key in about 0.1 milliseconds, regardless of "tree depth" because there is no tree.
Slow key generation is an operational concern. Many systems generate keys in production at startup; for hash-based signatures, this can mean a 30-second delay. Solutions include:
Pre-generate keys in a build pipeline. Use multi-tree variants (HSS, XMSS-MT) with smaller individual trees. Cache the tree on disk after generation; only regenerate when keys exhaust.
QNSQY pre-generates LMS trees during key creation and caches them in the user's keystore.
Trade-off 7: Signature Lifetimes vs Operational Profile
The total number of signatures a key can produce is fixed at key generation time. Choosing the right tree height depends on expected signature volume.
Code signing: thousands of signatures per year over decades. h equals 20 gives a million signatures, sufficient for most code-signing operations.
Document signing: tens to hundreds of signatures per year. h equals 16 (65k signatures) is sufficient and saves key generation time.
Firmware signing: a few signatures per device update cycle. h equals 10 (1024 signatures) may be sufficient.
Long-term archival: very few signatures over decades. h equals 10 to 16.
High-frequency signing (TLS, transaction signing, etc.): impractical for hash-based signatures. Use ML-DSA instead.
QNSQY's LMS at h equals 20 handles all typical code-signing and document-signing volumes. For higher-volume use cases, ML-DSA on the Pro tier is the better choice.
Trade-off Comparison Table at NIST Level 3
A side-by-side view of hash-based signature options at NIST Level 3 (192-bit classical security):
LMS L=H20/W=8 with SHA-256:
- Signature: 2820 bytes
- Verify time: 5 microseconds
- Sign time: 5 microseconds (with cached tree)
- Key gen: 30 seconds
- State management: required
XMSS-SHA2_20_256:
- Signature: 2820 bytes
- Verify time: 5 microseconds
- Sign time: 5 microseconds (with cached tree)
- Key gen: 30 seconds
- State management: required
SLH-DSA-192s:
- Signature: 16216 bytes
- Verify time: 4 milliseconds
- Sign time: 80 milliseconds
- Key gen: 30 microseconds
- State management: not required
For signature size: stateful schemes win (about 6x smaller). For sign time: stateful schemes win (about 16,000x faster) but require careful state. For key gen time: stateless wins (about 1 million times faster). For operational complexity: stateless wins.
The choice depends on operational profile.
Stateless Hash-Based Signature Speed Considerations
SLH-DSA has two parameter modes per security level: 's' (small signatures) and 'f' (fast signing).
SLH-DSA-128s: 7856 byte signatures, slow signing (about 600 ms). SLH-DSA-128f: 17,088 byte signatures, faster signing (about 8 ms). SLH-DSA-192s: 16,216 byte signatures, very slow signing (about 1.4 seconds). SLH-DSA-192f: 35,664 byte signatures, slower signing (about 25 ms). SLH-DSA-256s: 29,792 byte signatures, slow signing (about 3 seconds). SLH-DSA-256f: 49,856 byte signatures, slow signing (about 60 ms).
For high-frequency signing, the 'f' modes are necessary. For minimal signature size, 's' modes are necessary. For very high-security archival, SLH-DSA-256s is the most conservative choice with the smallest size, but signing takes seconds per message.
QNSQY supports SLH-DSA-128 and SLH-DSA-192 at both 's' and 'f' modes. Users pick based on their operational profile.
Trade-off 8: Standardization and Ecosystem Fit
Hash-based signatures are well-standardized but less widely deployed than lattice signatures.
Standards available:
LMS: RFC 8554 (2019), NIST SP 800-208 (2020). XMSS: RFC 8391 (2018), NIST SP 800-208 (2020). SLH-DSA: NIST FIPS 205 (2024).
Library support:
Mature: AWS LMS implementation, several IETF reference implementations. Newer: Many post-quantum libraries added LMS, XMSS, SLH-DSA in 2024-2025.
Ecosystem traction:
Cisco uses LMS in some infrastructure products. Some federal contractors use LMS or XMSS for compliance with SP 800-208. Most TLS and code-signing systems still use ML-DSA, ECDSA, or RSA.
For users who need NIST-approved hash-based signatures, the choice is well-supported. For broader interoperability, lattice signatures may be a better fit today.
Frequently Asked Questions
What is the biggest trade-off in hash-based signatures?
The stateful versus stateless trade-off. Stateful schemes like LMS and XMSS have small signatures but require careful state management. Stateless schemes like SLH-DSA have larger signatures but no state hazard.
Why is key generation slow?
Building a Merkle tree of height h requires 2^h hash operations. For h equals 20, that is about 2 million SHA-256 hashes, which takes about 30 seconds on a modern CPU. Lattice signatures avoid this by not using trees.
Can I use hash-based signatures for high-frequency operations?
No. Hash-based signatures are too slow and produce signatures too large for high-frequency use. Use ML-DSA instead. Hash-based signatures are best for code signing, document signing, and long-term archival.
What happens if I lose my LMS state?
You must regenerate the entire key. Reusing a key compromises the signing scheme. State management is the central operational hazard for stateful hash-based signatures.
Which hash-based signature does QNSQY support?
QNSQY supports LMS on the Business tier, with default tree height 20 and Winternitz w equals 8. SLH-DSA support is also available for users who prefer stateless signatures.
Sources
- NIST FIPS 205: Stateless Hash-Based Digital Signature Standard (2024). https://csrc.nist.gov/pubs/fips/205/final
- NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes (2020). https://csrc.nist.gov/pubs/sp/800/208/final
- RFC 8554: Leighton-Micali Hash-Based Signatures (McGrew, Curcio, Fluhrer, 2019). https://datatracker.ietf.org/doc/html/rfc8554
- RFC 8391: XMSS Extended Hash-Based Signatures (Hülsing et al., 2018). https://datatracker.ietf.org/doc/html/rfc8391
- NIST IR 8413: Status Report on the Third Round of the NIST PQC Standardization Process. https://csrc.nist.gov/pubs/ir/8413/final
Related Articles
- LMS Stateful Signatures
- XMSS Signatures Explained
- LMS vs XMSS
- ML-DSA vs SLH-DSA
- Merkle Trees: The Foundation of Hash-Based Signatures
Protect Your Data Before Q-Day Arrives
QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.