Stateful Hash-Based Signature Keys

XMSS, XMSS^MT, LMS and HSS are post-quantum signature schemes whose security rests only on a hash function (NIST SP 800-208, RFC 8391, RFC 8554). They sign through the same operations as every other signature key. What sets them apart is that the private key has state, and that state decides how many signatures the key can ever produce.

Why these keys have state

A stateful private key is a fixed set of one-time signing keys, each identified by an index. Every signature uses the next unused index, and an index must never be used twice: two signatures under the same index are enough for an attacker to forge signatures of that key. When every index has been used, the key can sign no more.

To guarantee that no index is ever reused, ANKASecure records each index as spent before the signature exists: it locks the key, takes one index, stores the advanced key, commits, and only then signs. If anything fails after the commit, that index is lost but never reused. Signatures by one key are therefore produced one at a time; different keys never wait for each other.

Verification has no state. Verifying a signature spends nothing, and every signature a key produced remains verifiable after the key is exhausted or rotated.

Other signature algorithms are not affected. ML-DSA, SLH-DSA, FALCON, RSA, ECDSA, EdDSA, SM2 and every composite key sign without state, in parallel and without limit. SLH-DSA is also hash-based, but stateless: it is the alternative when managing state is not acceptable, at the cost of larger and slower signatures.

Capacity of each key

An LMS or HSS key keeps its last index unused, so its capacity is one less than its tree size. Choose a parameter set whose capacity exceeds the signatures you expect over the key's life. Standards attribution and sizes are in the Simple Algorithms Catalog.

The two refusals

Rotate when the key is exhausted

Rotation creates new key material under the same kid. The new material starts again from index 0; the previous material is retired and keeps verifying everything it signed. Keep the exhausted key while its signatures still need to be verified, and rotate before it runs out: requests that fail after their index was committed (a client abort, a timeout) also consume indices.

Rotate after a database restore

A backup holds each stateful key as it was when the backup was taken. Signatures made after that moment used indices the backup still considers free, so a restored key would reuse them, and no system can tell afterwards how many indices were spent between the backup and the restore.

The platform therefore never lets a restored key sign. A restore performed with the platform's restore procedure records a restore marker (STATEFUL_KEY_STATE_RESTORED_AT), and every stateful key material created at or before it is refused with stateful-key-exhausted. Rotate each affected key: the new material is created after the marker and signs normally. Do not revoke the key as compromised: lost signing state is not key exposure, and that revocation would also stop its genuine signatures from verifying.