Stateful hash-based signatures (LMS and XMSS): the state-management catch

Short answer: LMS and XMSS are hash-based signature schemes whose security rests on the properties of hash functions rather than on factoring or discrete logarithms. Their catch is that they are stateful: the secret key changes with every signature, and if a key state is used twice, no security guarantee remains. NIST approved both in SP 800-208 and requires key and signature generation to happen in hardware cryptographic modules.

Two schemes, two RFCs

The Leighton-Micali Signature system (LMS) is specified in RFC 8554 (April 2019). The eXtended Merkle Signature Scheme (XMSS) is specified in RFC 8391 (May 2018). Both came out of the Internet Research Task Force. LMS builds on the Leighton-Micali One-Time Signature (LM-OTS) system. XMSS uses Winternitz One-Time Signature Plus (WOTS+) as its main building block, and RFC 8391 also defines a multi-tree variant, XMSS^MT. RFC 8554 includes a section comparing LMS with XMSS.

Why they are considered quantum-resistant

RFC 8391 says XMSS gives digital signatures without relying on the conjectured hardness of mathematical problems. It states that security is proven to depend only on the properties of cryptographic hash functions, and that XMSS stays secure even if the collision resistance of the hash function is broken. The same RFC notes that, unlike most other signature systems, hash-based signatures can so far withstand known attacks using quantum computers. "So far" matters: this is a statement about known attacks, not a proof against every future one.

The catch: the key changes over time

RFC 8554 says these schemes are stateful, meaning the secret key changes over time. If a secret key state is used twice, no cryptographic security guarantees remain. In practice that means a signer has to track state reliably. A restored backup, a cloned device or a crash that loses the latest state could all lead to reuse. Those examples are our illustration of the risk, not wording from the RFCs.

What NIST SP 800-208 says

According to the NIST CSRC page, SP 800-208 (October 2020) approves LMS and XMSS as part of the post-quantum cryptography effort, supplementing FIPS 186. It profiles both schemes and their multi-tree variants, and approves only some of the parameter sets in the RFCs. The approved sets use SHA-256 or SHAKE256 with 192-bit or 256-bit outputs. The profile also requires key and signature generation to be performed in hardware cryptographic modules that do not allow secret keying material to be exposed.

What this means for readers

Because of the state requirement, these schemes suit settings where one controlled signer produces a limited number of signatures, which is a common description of code and firmware signing. That is general reasoning and not a claim from the sources. This article describes the standards only. It does not describe any deployment, product or vendor implementation, and anyone planning to use them would need to read SP 800-208 and the RFCs directly.

FAQ

What are LMS and XMSS?

They are two stateful hash-based signature schemes. LMS is specified in RFC 8554 and XMSS in RFC 8391.

Why are they called quantum-resistant?

Their security relies on hash-function properties rather than on conjectured hard mathematical problems. RFC 8391 says hash-based signatures can so far withstand known attacks using quantum computers.

What does stateful mean here?

The secret key changes over time. If a key state is used twice, no cryptographic security guarantees remain.

Has NIST approved them?

Yes. SP 800-208, published October 2020, approves both schemes, with a limited set of parameter sets using SHA-256 or SHAKE256.

Where must keys be generated and used?

NIST SP 800-208 requires key and signature generation to be performed in hardware cryptographic modules that do not allow secret keying material to be exposed.