# LMS vs XMSS: Two Stateful Hash Signature Schemes **Source**: https://quantumsequrity.com/blog/lms-vs-xmss **Category**: PQC Algorithms --- [← Back to Blog](../../blog.html) PQC Algorithms # LMS vs XMSS: Two Stateful Hash Signature Schemes 10 min read NIST SP 800-208 approves two stateful hash-based signature schemes for federal use: [LMS](lms-stateful-signatures) and [XMSS](xmss-signatures-explained). Both are direct descendants of [Merkle's 1979 thesis](merkle-trees-cryptography). Both rest on the conservative assumption that hash functions are one-way and second-preimage resistant. Both produce signatures that survive any known quantum attack. Yet they have notable differences in tree structure, performance, parameter sets, and ecosystem traction. Choosing between them is a question many architects face when planning long-term post-quantum infrastructure. This post walks through the differences side by side, covers what RFC 8554 (LMS) and RFC 8391 (XMSS) each specify, and helps you understand why QNSQY chose LMS for its Business tier. ## Same Family, Different Optimizations Both LMS and XMSS were designed to refine Merkle's original 1979 hash-based signature scheme. Both use Winternitz one-time signatures and Merkle trees. The difference comes down to design choices made in the 2010s by separate teams. LMS was designed by David McGrew, Michael Curcio, and Scott Fluhrer at Cisco, published as RFC 8554 in 2019. It is a deliberately simple design favored for embedded and infrastructure use cases. XMSS was designed by Johannes Buchmann, Erik Dahmen, and Andreas Hülsing at TU Darmstadt, published as RFC 8391 in 2018. It uses tweakable hash functions for slightly stronger security proofs. Both became NIST SP 800-208 approved in 2020. Both are widely accepted in the cryptographic community. The choice between them is mostly about ecosystem and operational fit, not about fundamental security differences. A useful analogy: LMS and XMSS are like two different car manufacturers building near-identical sedans. Both have the same engine, same safety features, same fuel efficiency. Differences come down to how the dashboard is laid out and which suppliers each company partners with. You can drive either home safely. ## The Core Difference: Tweakable vs Plain Hashes XMSS uses tweakable hash functions. Each application of the hash within the scheme has a unique "tweak" or address that includes position information. The hash function family becomes a parameterized family rather than a single function. LMS uses ordinary hash functions but introduces position information via prefixes that get hashed along with the data. The hash function itself is unchanged; only the input format differs. Both designs achieve similar security in practice. The XMSS approach has a cleaner formal proof in the theory papers. The LMS approach is simpler to implement and audit. Most cryptographers consider this a wash. The deeper consequence: XMSS implementations look subtly different from LMS implementations even though they perform similar operations. Code reuse between the two is limited. ## Tree Structure and Multi-Tree Extensions For long signature lifetimes (more than 2^20 messages), both schemes use multi-tree variants. XMSS-MT (XMSS Multi-Tree) chains XMSS trees. The top tree's leaves are signatures from the next-level XMSS tree's keys. RFC 8391 specifies XMSS-MT with up to 2^60 signatures. LMS uses HSS (Hierarchical Signature System) for the same purpose. Same idea: a tree of trees, each lower tree authenticated by the tree above. RFC 8554 specifies HSS with up to 2^36 messages in some configurations and configurable depth. In practice, both achieve the same signature lifetimes with similar performance. HSS has slightly different parameter set conventions and a slightly simpler API. A picture: think of LMS as a single ladder you climb to reach a height. HSS extends it by stacking ladders end to end. XMSS-MT does the same with its own ladder design. Same height reached, slightly different ladder construction. ## Signature Size Comparison Signature size depends on tree height, Winternitz parameter, and hash size. At NIST Level 1 (h equals 10): XMSS-SHA2_10_256 signatures: about 2,500 bytes LMS L=H10/W=8 signatures: about 2,400 bytes At NIST Level 5 (h equals 20): XMSS-SHA2_20_256 signatures: about 2,820 bytes LMS L=H20/W=8 signatures: about 2,820 bytes At Level 5 with hash size 512: XMSS-SHA2_20_512 signatures: about 5,500 bytes LMS L=H20/W=8 with SHA-512 signatures: about 5,500 bytes The differences are within a few percent. Both schemes have signatures comfortably under 6 KB at the highest practical security levels. For comparison, [ML-DSA-65](mldsa-vs-slhdsa) signatures are about 3,309 bytes. SLH-DSA-128s signatures are about 7,856 bytes. LMS and XMSS sit in the middle. ## Verification Speed Verification speed depends on tree height (more levels equals more hash operations) and Winternitz parameter (higher w equals more hashes per signature). XMSS-SHA2_10_256 verification: about 5 microseconds on a modern CPU. LMS L=H10/W=8 verification: about 5 microseconds, similar to XMSS. Both are fast. Both are dominated by Winternitz signature verification (about 1700 hash operations) plus Merkle path verification (h hash operations). LMS has a small implementation advantage in some embedded contexts because it uses fewer hash invocations per signature. XMSS has a small advantage in formal correctness analysis. Neither matters for typical applications. ## Signing Speed and Key Generation Both schemes have slow key generation: building the entire Merkle tree requires hashing all 2^h W-OTS public keys, which can take seconds or minutes for large trees. XMSS key generation at h equals 20: about 30 seconds on a desktop CPU. LMS key generation at H equals 20: about 30 seconds, similar. Signing speed depends on whether you cache the Merkle tree (faster signing, more memory) or recompute paths on the fly (slower signing, less memory). Both schemes support both modes. XMSS signing with cached tree: about 1 millisecond. LMS signing with cached tree: about 1 millisecond. For comparison, [ML-DSA](mldsa-vs-slhdsa) signs in about 0.1 milliseconds and key-generates in 0.1 milliseconds. ML-DSA is far faster overall but uses lattice problems instead of hash functions. ## State Management Identical Both LMS and XMSS are stateful: the signer must track which W-OTS keys have been used. Reusing a key compromises the scheme. State management in both schemes follows the same pattern: Persist the next-key index to disk before signing. Use fsync to ensure the index is durable. Only release the signature after the index is committed. Multi-tree variants spread state across multiple trees but the core hazard remains: lose state, restore from a stale backup, or run on multiple machines without coordination, and you risk reuse. QNSQY's LMS implementation includes robust state management with atomic file writes, fsync, and reservation schemes. XMSS would use the same pattern. ## Why QNSQY Chose LMS When QNSQY added stateful hash-based signature support on the Business tier, the choice between LMS and XMSS was deliberate. LMS RFC 8554 has slightly wider deployment in production systems (Cisco infrastructure, several embedded and IoT vendors). The reference implementation has been audited intensely. LMS has a simpler API for the user. Tree height and Winternitz parameter are the only knobs. XMSS has tweakable hash configurations that add complexity. LMS multi-tree (HSS) is slightly simpler than XMSS-MT for typical deployments. Both schemes are equally secure under NIST SP 800-208 approval. The decision was based on operational simplicity, not security. QNSQY may add XMSS support in the future for users who need that specific scheme. For most applications requiring quantum-conservative signatures, LMS is the recommended choice. ## When to Use Either Over Lattice Signatures [ML-DSA](mldsa-vs-slhdsa) is the primary NIST post-quantum signature recommendation. It is faster, smaller, and stateless. Why use LMS or XMSS at all? Conservative security assumptions. Hash-based signatures rest only on hash function security. Lattice signatures rest on lattice problem hardness. If a major lattice algorithm appears, ML-DSA could be threatened. LMS and XMSS would survive. Long-term archival. For documents that need to remain verifiable for 50+ years, the conservative profile of hash-based signatures is appealing. Federal compliance. Some federal agencies prefer SP 800-208 approved schemes for specific use cases. For most users, [hybrid signatures](hybrid-encryption) using ML-DSA combined with Ed25519 hit the right balance. For users who need maximum quantum-conservatism, LMS on the QNSQY Business tier is the right choice. ## Migration and Interoperability Concerns If you adopt LMS today, can you switch to XMSS later? Not directly. The signature formats are different. Verifiers need to know which scheme was used and run the matching verification code. For long-term archival, this matters. A document signed with LMS today must be verifiable in 2050 by software that still supports LMS. RFC 8554 is stable, so any 2050 implementation should still work, but it is something to plan for. The same applies to XMSS RFC 8391. Both standards are stable but separate. A common migration pattern: run both LMS and XMSS in parallel, signing important documents with both. Verifiers can use whichever they prefer. This doubles the signature size but provides defense in depth. For QNSQY users, sticking with LMS is fine. If a future need arises for XMSS, switching is possible by re-signing critical documents with both schemes. ## Why Not Just Use SLH-DSA? A natural question: if you want hash-based signatures and want to avoid state management, why not just use SLH-DSA (FIPS 205)? Why bother with LMS or XMSS at all? Three reasons: Signature size. SLH-DSA-128s signatures are about 8 KB. LMS or XMSS at the same security level is 2.5 to 3 KB. For high-volume signing, the 3x size difference matters. Speed. SLH-DSA signing requires hashing the entire FORS forest, which can take 10 ms or more. LMS signing is closer to 1 ms. Compliance preferences. Some federal agencies prefer SP 800-208 approved schemes (LMS, XMSS) over FIPS 205 (SLH-DSA) for specific use cases. For users who prefer the smaller signatures and faster signing, LMS or XMSS is the right choice. For users who prefer no state management, SLH-DSA is the right choice. QNSQY's Business tier supports both. ## Practical Adoption Scenarios LMS is well-suited to: Code signing where signature lifetimes exceed 20 years. Firmware verification on devices with multi-decade lifecycles. Document archives with strict integrity requirements. Federal systems following SP 800-208 guidance. XMSS is well-suited to: Academic research and prototype implementations. Systems where the formal security proof matters more than ecosystem fit. Federal systems following SP 800-208 guidance with XMSS preference. Neither is well-suited to: High-frequency signing (hundreds per second) where ML-DSA's speed wins. Stateless environments where state management is impractical. Low-resource embedded chips where 3 KB signatures are too large. For QNSQY users on the Business tier, LMS handles the niche use cases where hash-based signatures are clearly preferred. ## Frequently Asked Questions ### Are LMS and XMSS compatible? No. They are independent designs with different signature formats, hash function parameterizations, and verification procedures. An LMS signature cannot be verified by XMSS code and vice versa. ### Which has stronger security? Both are equally secure in practice under NIST SP 800-208. XMSS has slightly cleaner formal proofs due to tweakable hashes. LMS has slightly simpler implementation. The security difference is theoretical, not practical. ### Is LMS faster than XMSS? Both have nearly identical performance. Signing, verification, and key generation take similar times. Differences are within measurement noise on most systems. ### What size signatures do they produce? About 2.5 to 5.5 KB depending on configuration. XMSS-SHA2_20_256 and LMS L=H20/W=8 both produce about 2.8 KB signatures at NIST Level 5. ### Why is QNSQY using LMS instead of XMSS? QNSQY chose LMS for ecosystem fit and simpler operational model. Both are equally NIST-approved. XMSS support may be added later. The Business tier provides hash-based signatures via LMS for users who need maximum quantum-conservatism. ## Sources 1. RFC 8554: Leighton-Micali Hash-Based Signatures (McGrew, Curcio, Fluhrer, 2019). https://datatracker.ietf.org/doc/html/rfc8554 2. RFC 8391: XMSS Extended Hash-Based Signatures (Hülsing, Butin, Gazdag, Rijneveld, Mohaisen, 2018). https://datatracker.ietf.org/doc/html/rfc8391 3. NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes (2020). https://csrc.nist.gov/pubs/sp/800/208/final 4. Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., Mohaisen, A. (2017). "XMSS: A Standardized Stateful Hash-based Signature Scheme." IETF cfrg. https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-xmss-hash-based-signatures-12 5. 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](lms-stateful-signatures) - [XMSS Signatures Explained](xmss-signatures-explained) - [Merkle Trees: The Foundation of Hash-Based Signatures](merkle-trees-cryptography) - [ML-DSA vs SLH-DSA](mldsa-vs-slhdsa) - [Hash-Based Signature Trade-offs](hbsig-tradeoffs) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing.html)