Day 6: SLH-DSA — Hash-Based Signatures

Phase 3 · July 13, 2026

Agenda (2–3 hours)

• Read (60 min): NIST FIPS 205 §1–4 (SLH-DSA overview and construction); RFC 8391 (XMSS — a related hash-based scheme, more accessible)
• Study (45 min): Merkle tree signatures, one-time signatures, stateful vs. stateless
• Challenge (45 min): Explain when to use SLH-DSA vs. ML-DSA for a PKI

Why Hash-Based Signatures?

ML-DSA and FN-DSA security rests on lattice problems — relatively new assumptions.
Hash-based signatures rely only on the collision resistance of a hash function.

If SHA-256/SHA-3 is secure, hash-based signatures are secure. Period.
No lattice assumptions. No algebraic structure. Just hashing.

This makes them the most conservative PQC option — preferred for root CAs
that sign rarely but whose keys must be trusted for decades.

One-Time Signatures: The Foundation

Lamport signatures (1979): the original one-time signature scheme.

KeyGen: for each bit of the message:
        generate two random 256-bit values (0-key, 1-key)
        public key = SHA-256 of each value

Sign(m): for each bit i of m:
         reveal private_key[i][bit_i]

Verify: check SHA-256(revealed_value) matches public key

One-time only: revealing one key pair leaks information about the private key.
Sign the same key twice → private key recovery possible.

This is the fundamental building block. SLH-DSA builds on top to handle many signatures.

From One-Time to Many-Time: Merkle Trees

Root = Hash(H(leaf_0), H(leaf_1), ..., H(leaf_n))
        ↑
  sign this with a one-time key

leaf_i = OTS public key for the i-th signature

Signing message k: use leaf_k's one-time key, include Merkle inclusion proof.
Verifying: verify OTS, verify Merkle path up to root.
Root = the long-term public key.

Each leaf = one signature. Tree depth determines how many signatures you can make.

Stateful vs. Stateless: The Critical Difference

Stateful (XMSS, LMS — NIST SP 800-208):

• Must track which leaf was used last
• Reusing a leaf = catastrophic key exposure
• Hard to use safely in distributed systems (who tracks the counter?)
• Suitable for: single-device signing, hardware security keys

Stateless (SLH-DSA / SPHINCS+):

• Uses a randomized path selection — no counter needed
• Each signature picks a random leaf via a pseudorandom function of the message
• Safe to use concurrently without coordination
• Tradeoff: larger signatures, slower

For distributed PKI services: SLH-DSA is the appropriate choice.

SLH-DSA Parameters

s = "small" (smaller signatures, slower signing)
f = "fast" (faster signing, larger signatures)

For root CA (signs rarely, must be trusted long-term): SLH-DSA-SHA2-256s.
For anything that signs frequently: use ML-DSA instead.

Challenge Assignment

Write a 1-page recommendation: which signature algorithm for each CA tier?

Revisit your algorithm selection matrix from Day 5 and refine the CA cert rows:

1. Root CA — SLH-DSA or ML-DSA? Why? Consider: signing frequency, key longevity, need for HSM support, signature size in the chain.
2. Intermediate CA — same analysis.
3. Leaf certs — same analysis, but also consider: TLS handshake overhead, frequent issuance, client verification cost.

Then: what is the certificate chain size (bytes) for a 3-cert chain if:

• Root uses SLH-DSA-SHA2-256s
• Intermediate uses ML-DSA-65
• Leaf uses ML-DSA-44

Compare to a classical 3-cert ECDSA chain. What is the TLS handshake overhead?

Resources

• NIST FIPS 205: SLH-DSA standard
• NIST SP 800-208: Stateful hash-based signature schemes (XMSS, LMS)
• RFC 8391: XMSS (related, more accessible description of hash-based trees)
• "Sphincs+" paper: sphincs.org — original SPHINCS+ specification