Engineering · 2026-04-24
Stateful Hash-Based Signatures for Audit Logs: LMS and XMSS for One Signer
By J. W. Bouckaert
Most post-quantum migration plans treat signatures as one switch: replace RSA and ECDSA with ML-DSA (FIPS 204) and move on. That is the right default for general-purpose signing such as TLS certificates, tokens and software releases with several signers. Append-only audit logs are a different workload, and for them a stateful hash-based scheme is worth considering.
This article compares the three NIST post-quantum signature families for audit logs, explains the state requirement that makes LMS and XMSS hard to run safely, and says where each fits. It ends with what PasskeyBridge does today.
Three families of post-quantum signatures
| Family | Standard | Security rests on | Stateful | Intended use |
|---|---|---|---|---|
| Lattice | FIPS 204 (ML-DSA) | Module-LWE and Module-SIS hardness | No | General-purpose signatures |
| Stateless hash-based | FIPS 205 (SLH-DSA) | Properties of the hash function | No | General-purpose, conservative alternative |
| Stateful hash-based | SP 800-208 (LMS, HSS, XMSS, XMSS^MT) | Properties of the hash function | Yes | Restricted to settings that can manage state |
FIPS 204 and FIPS 205 were published in August 2024. SP 800-208 was published in October 2020 and approves LMS and HSS as specified in RFC 8554 and XMSS and XMSS^MT as specified in RFC 8391.
Sizes
Signature and public key sizes follow from the parameter sets. Timings depend on platform and implementation, so none are given here.
| Scheme and parameters | Public key | Signature |
|---|---|---|
| LMS_SHA256_M32_H15 with LMOTS_SHA256_N32_W8 | 56 bytes | 1,612 bytes |
| HSS, two levels of the above (L=2) | 60 bytes | about 3,284 bytes |
| XMSS-SHA2_10_256 | 68 bytes | 2,500 bytes |
| ML-DSA-65 | 1,952 bytes | 3,309 bytes |
| SLH-DSA-SHA2-128s | 32 bytes | 7,856 bytes |
| SLH-DSA-SHA2-128f | 32 bytes | 17,088 bytes |
A single-level LMS signature is about half the size of an ML-DSA-65 signature. A two-level HSS signature, which is what a long-lived signer needs, is about the same size as ML-DSA-65. The public keys of the hash-based schemes are far smaller.
Capacity
An LMS tree of height 15 has 2^15 = 32,768 one-time keys. A two-level HSS key with height 15 at each level has 2^30, about 1.07 billion. Each signature consumes one leaf, permanently. Capacity planning is simple arithmetic: if a log signs one checkpoint every five minutes, that is 288 signatures a day, and a single height-15 tree lasts about 113 days. Signing every row of a busy log is a different matter and would exhaust even a large HSS key quickly.
The state requirement
The danger with LMS and XMSS is reusing a one-time key. Signing two different messages with the same leaf can give an attacker enough information to forge signatures, and the public key keeps verifying normally, so the compromise is not visible. The signer must therefore record that a leaf is used before it releases a signature, and must never go back to an earlier state, for example through a backup restore or a cloned virtual machine.
SP 800-208 addresses this by requiring key generation and signing to take place in a hardware cryptographic module that does not allow the private key to be exported. That rules out a plain software signer for federal use, and it means the module must handle the state counter.
A careful design has these properties:
- One signer per key. No load-balanced pool, no active-active replicas holding the same key.
- Advance before release. The counter is persisted before the signature leaves the module. A crash may burn a leaf; it must never reuse one.
- No restore to an older state. Backups that would roll the counter back are not usable for signing.
- Rotation before exhaustion. Monitor the share of leaves used and plan a new key well before the tree runs out.
Hash-based security for logs
Audit records may need to stay verifiable for many years. Hash-based signatures rest only on properties of the hash function, which is a smaller set of assumptions than lattice schemes require. Lattice problems are widely believed to be hard and ML-DSA is the general-purpose standard; the point is that a long-lived archive benefits from the most conservative assumptions available. During the NIST process, two other signature and key-exchange candidates, Rainbow and SIKE, were broken by classical attacks, which is a reminder that newer assumptions carry more uncertainty.
Poor fits for stateful signatures
- Token issuance across several regions. Concurrent signers cannot share one state safely.
- Ephemeral or autoscaled workers. They cannot hold state durably.
- End-user devices. Devices can be cloned or restored from backup.
- Code signing from several build systems. Two signers would need one canonical counter.
For these, ML-DSA is the default post-quantum choice, with SLH-DSA as the stateless hash-based alternative where its larger signatures are acceptable.
Signing checkpoints instead of rows
Signing every row multiplies signature storage and verification by the number of rows. A common alternative is to hash-chain the rows, so each row commits to the one before it, and sign only periodic checkpoints over the chain head. One signature then covers every row written since the previous checkpoint, and an edit to any earlier row breaks the chain. This also changes the capacity picture for stateful schemes: a few hundred signatures a day fits comfortably in an LMS or HSS key.
PasskeyBridge today
PasskeyBridge's audit log is hash-chained. Every five minutes a scheduled job builds a checkpoint over the chain heads, binds it to the previous checkpoint and, when it is reachable, the latest NIST Randomness Beacon pulse, and signs it with a hybrid HMAC-SHA-256 and ML-DSA-65 signature. The public verification key and the verification steps are published. PasskeyBridge does not use LMS, XMSS or SLH-DSA. For more on its post-quantum signing, see the post-quantum identity stack overview and hybrid signatures.
Summary
For an append-only log with a single signer and a modest signing rate, LMS or HSS gives small public keys, signatures at or below ML-DSA size, and hash-only security assumptions, at the cost of strict state handling in a hardware module. Signing periodic checkpoints over a hash chain keeps the signing rate low enough for that to be practical. ML-DSA remains the right default for everything that cannot guarantee a single, stateful signer.