06 — The Stateless Property

What "Stateful" Means

A stateful signature scheme requires the signer to remember what they've done:

Stateful signer:
  1. Check index counter: "Next available key is #42"
  2. Sign with key #42
  3. Increment counter: "Next available key is #43"
  4. Save state to disk

If the state is lost or corrupted:

• You might reuse key #42 → forgery
• You might skip keys → wasted capacity

Real-World Stateful Problems

SLH-DSA Is Stateless

SLH-DSA eliminates the state entirely:

Stateless signer:
  1. Take message + public key seed
  2. Compute: path = Hash(message || pk_seed || random_salt)
  3. Derive signing keys along path from master seed
  4. Sign with derived keys
  5. No state to save!

The message itself determines which keys to use. No counter. No database. No synchronisation.

How Key Derivation Works

Instead of pre-generating and storing millions of keys, SLH-DSA derives them on demand:

Master Seed (secret, 32 bytes)
   |
   v
Pseudorandom Function (PRF)
   |
   +-- Message hash + path index --> WOTS+ secret key #1
   +-- Message hash + path index --> WOTS+ secret key #2
   +-- ...
   +-- Message hash + path index --> FORS secret key

The PRF (typically SHA-256 in a specific mode) expands the master seed into any key needed. As long as the master seed is secret, all derived keys are secret.

Security Implications

The Good

The Caveat: Message-Dependent Paths

Same message → same path → same keys. This is fine for legitimate re-signing but:

• An attacker who can choose messages might try to force path collisions
• The random salt in the signature prevents this (different salt → different path)
• Even without salt, the probability of accidental collision is negligible

Formal Security

SLH-DSA's security proof shows:

• Existential unforgeability: No attacker can forge a signature without breaking the hash function
• Statelessness: The proof holds even when the signer has no memory of previous signatures
• Multi-target protection: The bitmasks (WOTS+) and salt prevent multi-target attacks

Stateless vs. Stateful: When to Choose

Resources

• Hülsing et al., "SLH-DSA specification" (2022), NIST PQC Round 3 submission
• NIST FIPS 205, Section 4: Security and Stateless Property
• RFC 8554: Leighton-Micali Hash-Based Signatures (LMS, stateful)