Engineering · 2026-04-24

Stateful Hash-Based Signatures for Audit Logs: When LMS/XMSS Outperforms Lattice Schemes

By J. W. Bouckaert

Most post-quantum migration plans treat the problem as a single switch: rip out RSA and ECDSA, drop in ML-DSA-65 (FIPS 204), update the certificate authority, ship the binary. That treatment is correct for general-purpose signatures—TLS certificates, JWT bearer tokens, software updates with multiple distributors. It is the wrong treatment for a class of signing workloads that are quietly the most cryptographically demanding part of the stack: append-only audit logs.

Audit logs sign more messages per day than every other component combined. A single mid-sized SaaS tenant on PasskeyBridge writes between two and twenty million audit rows per day, each one signed under the tenant's hash-chained log key. Multiply by signature size and verification cost, and the audit pipeline alone consumes more cryptographic work than authentication, attestation, and webhook delivery put together. The choice of signature algorithm for the audit log is therefore the dominant cost center of the post-quantum migration.

This article makes the case that for this specific workload—append-only writes, predictable signing cadence, single trusted signer—the right algorithm is a stateful hash-based scheme rather than lattice-based ML-DSA: LMS as approved by NIST SP 800-208 and standardized in RFC 8554, or XMSS as standardized in RFC 8391. The security assumptions are simpler, the signatures are smaller, the verification is faster, and the only meaningful cost—state management—is something an audit log already does for free.

The three families of post-quantum signatures

NIST's post-quantum portfolio in 2026 contains three signature families, each with distinct cryptographic foundations and operational profiles. Treating them interchangeably is the most common mistake in PQC migration planning.

The three families differ on two axes that matter operationally: the security reduction (what mathematical problem an attacker must solve to forge a signature) and the state requirement (what the signer must remember between operations).

Lattice schemes derive their security from the conjectured hardness of Module-LWE, a problem that has been intensively studied since 2010 but is younger and has seen fewer years of cryptanalysis than the discrete log or factoring problems that underpin classical cryptography. Hash-based schemes—both stateful and stateless—reduce their security to the preimage and collision resistance of the underlying hash function, properties that have been studied for fifty years and that already underpin the integrity of every binary on Earth.

The operational distinction between the two hash-based variants is state. SLH-DSA (FIPS 205) carries no state between signatures and is therefore safe to deploy in settings where the signer might be cloned, replicated, or restored from a backup. The price is signature size: SLH-DSA-SHA2-128f produces 17 KB signatures, roughly ten times the size of LMS at the same security level. LMS and XMSS produce small signatures—1.7 to 2.5 KB at the recommended parameters—but require the signer to track which one-time key indices have been used and to refuse to ever reuse one. State reuse in LMS is catastrophic: a single duplicate index allows the attacker to forge arbitrarily.

Audit logs as an LMS workload

Three properties make audit logs an unusually clean fit for stateful hash-based signatures, and the same three properties make them an unusually poor fit for lattice schemes.

Append-only writes. An audit log, by definition, only grows. Every row is written exactly once and never modified. There is no concurrent multi-writer scenario in which two replicas might try to sign with the same key index, because the log itself is single-writer at the tenant boundary. This eliminates the worst-case failure mode for stateful schemes—accidental state reuse from concurrent signers.

Predictable signing cadence. A high-traffic tenant signs roughly 25 audit rows per second on average and bursts to perhaps 200 per second during incident response. Across the 90-day rotation window of an LMS_H15 key (which permits 32,768 signatures at the leaf level, expanded by HSS hierarchy), this matches up almost exactly: 32,768 signatures across 90 days is 4.2 signatures per minute average, well within capacity, and the HSS top-level tree easily accommodates the burst rate. The signing budget is knowable in advance; key rotation can be scheduled deterministically.

Single trusted signer. Each tenant's audit log is signed by exactly one keypair held inside the tenant's HSM-backed key management subsystem. There is no scenario in which a second signer might independently advance the state. The state counter is co-located with the log itself in a strongly consistent transactional store, and state advancement is committed atomically with the log row. If the transaction fails, the row is not written and the counter is not advanced.

By contrast, every other signature workload in the platform—JWT issuance, attestation receipts, webhook signatures—has at least one of these properties absent. Multiple regional issuers sign JWTs concurrently. Attestation receipts can be issued by ephemeral worker pods. Webhook signatures need to be reproducible after a key restore. For all of those, the lattice-based ML-DSA is the correct choice. The audit log is the one workload where the constraints align with LMS's preconditions.

Quantitative comparison

The following measurements come from a million-iteration benchmark on AWS Graviton4 (c8g.4xlarge, single-thread, hardware AES disabled to remove unrelated noise). All implementations are FIPS-validated reference code: ML-DSA from BoringSSL's PQ branch, SLH-DSA from the official NIST reference implementation, and LMS from Cisco's reference implementation cited in RFC 8554.

Three observations follow from the table.

First, LMS produces signatures roughly half the size of ML-DSA and one-tenth the size of SLH-DSA-128f. For an audit log writing twenty million rows per day, the difference between LMS at 1.7 KB and ML-DSA at 3.3 KB is 30 GB of additional storage per tenant per day—which compounds across the seven-year retention window mandated by SOC 2 evidence rules.

Second, LMS verification is faster than every other PQC option, including ML-DSA. For an audit log whose primary read pattern is compliance review—where every row signed in a given period must be verified during evidence preparation—a 25% verify-side speedup translates to meaningful audit-cycle reduction.

Third, LMS sign-side throughput (~1,000 signatures per second per core) is more than sufficient for the predictable cadence of an audit log. ML-DSA's higher sign throughput is irrelevant when the workload is rate-limited by the log's natural write cadence.

The security reduction

Cryptographic security is a question of the depth and breadth of the assumption you are willing to bet on, and only rarely one of absolute proof. Lattice and hash-based schemes ask for very different bets.

ML-DSA's security rests on the conjectured hardness of Module Learning With Errors (Module-LWE) and Module Short Integer Solution (Module-SIS). These problems are members of a family that has been intensively studied since the late 2000s, with no known polynomial-time classical or quantum algorithm. They are believed to be hard. They are not, however, as deeply studied as the integer factorization or discrete logarithm problems that underpin RSA and ECDSA. Several lattice schemes proposed during NIST's PQC standardization process were broken during the competition itself—not Kyber or Dilithium, but enough adjacent constructions to remind us that the field is young.

LMS and XMSS reduce their security to the preimage resistance, second-preimage resistance, and collision resistance of the underlying hash function (SHA-256 in the standard parameter sets). These are properties that have been intensively studied for over fifty years. SHA-256 is the hash function that underpins TLS certificates, code signing, the Bitcoin blockchain, every Linux distribution's package signatures, every container image digest, and the entire PKI ecosystem. If SHA-256 collision resistance breaks, the cryptographic apocalypse extends well beyond your audit log.

This is not an argument that lattice schemes are insecure; they almost certainly are not. The argument is that hash-based security is simpler—that fewer mathematical primitives are involved, that the security reduction is shorter, and that an attacker capable of breaking SHA-256 has bigger problems to occupy them than your audit pipeline. For a workload where the cost of a subtle break is unbounded (every historical audit row potentially repudiable), the simpler bet is the safer bet.

This is the same conservative reasoning that drove the adoption of hybrid signatures for identity assertions: dual-sign with a classical and a post-quantum scheme so a break in either one does not compromise the system. For audit logs, the equivalent move is simpler: choose the post-quantum scheme whose security assumption is already underwritten by the rest of the cryptographic world.

State management done right

The catastrophic failure mode of LMS is state reuse. SP 800-208 §3.1 is unambiguous on the requirement: the next-unused-index counter must be advanced and persisted to non-volatile storage before the signature is emitted from the signer. Anything less—holding the counter in volatile memory, advancing it after emission, syncing asynchronously—creates a window in which a crash or restore could cause the same index to be reused.

A correct implementation has four properties:

1. Monotonic counter in HSM. The next-index counter lives inside the same FIPS 140-3 hardware security module that holds the private key. The HSM exposes an atomic "consume next index" operation that returns the index and immediately advances the persisted counter, all within a single transaction.

1. Atomic commit with the log row. The audit-log INSERT and the signature emission share a single database transaction. If either step fails, both roll back, and the consumed index is not released back to the pool—the counter advances regardless of whether the row is ultimately written. Burning an index is far cheaper than risking reuse.

1. No backup-restore loop. The HSM's counter cannot be restored from a backup that is older than the most recent signature. This is enforced by the HSM itself: backups capture the counter value at backup time, and any restore that would lower the counter is rejected.

1. Geographic replication is one-way. When the audit log is replicated to a secondary region, signature verification is performed in the secondary region, but signature emission is performed only in the primary. There is exactly one signer for each tenant, and failover requires explicit re-keying rather than automatic promotion of the secondary's key state.

These constraints are not exotic. Every well-designed audit log already satisfies them, because tamper-evidence requires a single-writer architecture with strongly consistent commits. LMS state requirements layer onto the existing audit-log architecture without adding meaningful complexity. The design exercise is "make sure the counter advance is in the same transaction as the log row insert," and that is a one-line constraint in any modern database.

For a deeper treatment of the HSM-backed counter pattern in our implementation, see the architectural notes in our post-quantum identity stack overview, which describes the same hardware boundary used for ML-DSA private keys in the authentication path.

Workloads that should not use LMS

This article is making a narrow argument, and the narrowness matters. LMS is the right answer for audit logs and for nothing else in the typical identity stack. The following workloads should not use stateful hash-based signatures:

• JWT issuance. Multiple regional issuers sign concurrently; stateless ML-DSA is the correct choice.
• Webhook signatures. Need to be reproducible after key restore; SLH-DSA or ML-DSA fits better.
• Attestation receipts from ephemeral workers. Ephemeral signers cannot hold state safely.
• End-user device signatures. Devices can be cloned, restored from backup, or run multiple OS instances; assume state safety is impossible.
• Code signing across multiple build farms. If two build farms might sign the same artifact, neither can hold the canonical state.
• Any signature operation behind a load-balanced pool. The pool semantics defeat single-signer assumptions.

For all of these, ML-DSA (FIPS 204) is the right post-quantum choice; for ultra-conservative deployments where state safety can be guaranteed but signature size is irrelevant, SLH-DSA (FIPS 205) is the conservative fallback.

This taxonomy matters because the wrong choice is silently catastrophic in both directions. An ML-DSA deployment for an audit log spends 2× the storage and 1.4× the verification cost forever, with no benefit. An LMS deployment for a JWT issuer creates a state-reuse vulnerability that produces silent forgery as soon as two workers initialize. Knowing which workload sits on which side of the line is the design discipline.

Implementation checklist

For teams considering LMS for an audit pipeline, the following checklist captures the implementation requirements that experience has shown are the most often missed.

• Choose parameters with rotation in mind. LMS_SHA256_M32_H15 with W=8 gives 32,768 signatures per leaf tree; HSS with two levels (L=2) gives ~10⁹ signatures total. Size your tree depth to your rotation cadence: a 90-day rotation at 200 signatures per second needs at least 1.6 billion indices, comfortably inside HSS L=2.
• Provision HSM-backed counters. AWS CloudHSM, Azure Dedicated HSM, and Google Cloud HSM all support custom firmware capable of holding the LMS index counter atomically with the private key. Cloud KMS without dedicated HSM is not sufficient because the counter is not exposed atomically with sign operations.
• Use HSS, not raw LMS. HSS (Hierarchical Signature Scheme) wraps multiple LMS trees so the working tree can rotate without re-publishing the public key. RFC 8554 §3.3 specifies HSS; raw LMS without HSS exhausts in tens of thousands of signatures.
• Test the burn path. Build a test harness that forces an index burn (consumed but not used) and confirm that the next signature uses the next-next index. Many implementations leak indices on failure; that is correct behavior.
• Plan key rotation 30 days before exhaustion. Set up monitoring on counter percentage-used and alert at 70% to give comfortable runway for tenant-coordinated rotation.
• Capture the zero-knowledge audit-trail architecture tenant-isolation properties. LMS keys are per-tenant; cross-tenant audit replay is impossible by construction.

A well-implemented LMS audit-log signer is genuinely simpler than the equivalent ML-DSA implementation, because the state-management invariants align with the database's existing transactional semantics. The complexity moves from cryptographic library configuration into a single database constraint.

Audit logs in the PQC migration

Audit logs are not the most visible part of the post-quantum migration, but they are the largest by volume and the longest by retention. A signature emitted today on an audit row about a 2026 transaction must remain verifiable in 2033, when the seven-year SOC 2 evidence-retention window closes. That signature must therefore be quantum-secure against today's threat model and across the entire seven-year harvest-now-decrypt-later horizon.

A pure ML-DSA audit log is acceptable for this requirement. An LMS audit log is also acceptable and is operationally cheaper. The argument here is narrower than "LMS or nothing": it is "stop reflexively using lattice schemes for every PQC workload, because the right tool for each workload is determined by the workload's own properties rather than the cryptographic family's prominence."

For PasskeyBridge, the production split is: ML-DSA for authentication and attestation, LMS for the per-tenant audit log, ML-KEM for key encapsulation in token transport, and SLH-DSA reserved for compliance-mandated dual-signing in regulated tenants. Each scheme is doing the job it was designed for. None of them is doing every job.

This is the discipline that distinguishes a competent PQC migration from a marketing one. Deploying ML-DSA does not finish the migration. The migration is finished when each workload is signed with the algorithm whose security model and operational profile align with that workload's actual requirements. For audit logs, that algorithm is LMS, and the analysis is over.

Read the PasskeyBridge security architecture →

Start free · Test the API