SLH-DSA
Every other signature scheme in use rests on a mathematical problem that someone might one day solve: factoring, discrete logarithms, lattices, isogenies. SLH-DSA rests only on its hash function behaving like one. That makes it the most conservative choice there is, and its signatures run from about 8 to 50 kilobytes.
- Status
- FIPS 205, August 2024
- Rests on
- Security properties of the hash function, SHA-2 or SHAKE
- Sizes
- SLH-DSA-128s: 32-byte public key, 7,856-byte signature; SLH-DSA-128f: 17,088 bytes, faster signing
- Signatures per key
- Designed for up to 264, with no state to keep
- Quantum
- Only generic speedups, which the parameters account for
One-time signatures from hash chains
The building block is a one-time signature. In the Winternitz scheme, WOTS+ in its modern form, the private key is a list of random strings, and the public key is what you get by hashing each of them w − 1 times. Every string starts a chain of hashes, and the public key is the list of chain ends. To sign, write the message digest in base w, and for each digit v reveal the value v steps along the corresponding chain. The verifier hashes each revealed value the remaining w − 1 − v times and checks that it lands on the public key. Going forward along a chain is easy; going back would mean inverting the hash.
That leaves one problem: anyone can hash a revealed value further, which turns a signature on digit v into one on any larger digit. A checksum closes it. The signer also signs the sum of w − 1 − v over all the digits, and raising any message digit lowers that sum, which would need going backwards on a checksum chain.
The build signs "release v1.0" with a key of SLH-DSA-128's shape: n = 16-byte values, w = 16, 32 message digits and 3 checksum digits, so 35 chains and a 560-byte signature. The hash here is SHA-256 cut to 16 bytes. Signing took 195 hash evaluations and verification 330, which add up to the 525 steps of all the chains. The signature verifies, and it does not verify for "release v1.1".
Why one-time means one time
Each signature reveals a point on every chain. After several signatures under one key, an attacker knows, for each chain, the lowest point anyone has revealed, and can sign any message whose digits are all at least those lowest points, checksum included. Finding such a message is a matter of hashing random candidates. The build signed a growing number of messages with a single key and searched:
| Messages signed | Tries to a forgery | Verified |
|---|---|---|
| 1 | none in 300,000 | — |
| 2 | none in 300,000 | — |
| 3 | none in 300,000 | — |
| 4 | 23,541 | Yes |
| 6 | 39 | Yes |
| 8 | 25 | Yes |
With up to 3 signatures the search found nothing in 300,000 tries. With 4 it took 23,541 tries, and with 8 only 25. Each forgery was then assembled from the revealed chain values and verified against the original public key. A one-time key used a few times is not slightly weaker. It is broken.
Many keys: Merkle trees
To sign more than once, Merkle's 1979 construction commits to many one-time keys at once. Hash the one-time public keys in pairs, then hash the results in pairs, until a single root remains, and publish the root as the public key. A signature is then a one-time signature plus the authentication path: the sibling of each node on the way from the used leaf to the root. The verifier recomputes the leaf from the one-time signature and hashes up the path.
The build puts 16 one-time keys under a tree of height 4 and signs "release v2.0" with leaf 5. The signature is the 35 chain values and 4 path nodes, 624 bytes, and it hashes up to the root a9738a0d40cdaa4176a716a8ca2a38fe.
This scheme is stateful: the signer must never use a leaf twice, so it has to remember which leaves are spent, across crashes, backups and cloned virtual machines. LMS and XMSS, standardised in NIST SP 800-208, work this way and are approved for uses like firmware signing, where the state can be controlled. For general use, a state that can be lost or duplicated is a liability, since the table above shows what reuse costs.
Removing the state
SLH-DSA, designed as SPHINCS+ by Bernstein, Hülsing and others, removes the state by making the tree so large that a leaf chosen pseudorandomly from the message is essentially never reused. It needs two further ideas to make that affordable:
- A hypertree. A single tree of height 63 could never be built, so the tree is split into d layers of smaller trees, each of height h/d. Every tree's root is signed with a one-time key from the tree above, and only the trees on the path to the chosen leaf are ever computed.
- FORS at the bottom. The message itself is signed with a few-time signature, FORS, rather than a one-time one. It consists of k Merkle trees of height a, and each signature reveals one leaf from each. Even when the pseudorandom leaf choice does repeat, a few signatures under one FORS key cost a little security rather than all of it.
A signature is therefore a randomiser, a FORS signature, and d layers of WOTS+ signature plus authentication path. With n-byte hashes that is n(1 + k(a + 1) + h + d·len) bytes, where len is the number of WOTS+ chains. The formula reproduces every size in the standard:
| Parameter set | n | h | d | Signature bytes |
|---|---|---|---|---|
| SLH-DSA-128s | 16 | 63 | 7 | 7,856 |
| SLH-DSA-128f | 16 | 66 | 22 | 17,088 |
| SLH-DSA-192s | 24 | 63 | 7 | 16,224 |
| SLH-DSA-192f | 24 | 66 | 22 | 35,664 |
| SLH-DSA-256s | 32 | 64 | 8 | 29,792 |
| SLH-DSA-256f | 32 | 68 | 17 | 49,856 |
The "s" sets are small and slow to sign, the "f" sets fast and larger. FIPS 205 states that each set is designed to stay secure for up to 264 signatures per key. Its security claim is in NIST's category terms: at least as hard to break as AES-128, AES-192 or AES-256 key search for n = 16, 24 or 32.
Where it fits
SLH-DSA's security argument is the shortest of any standard signature: if the hash function is sound, so is the scheme. A quantum computer only gets Grover-type speedups against hash functions, which the parameters already absorb. What it costs is size and time. A 7,856-byte signature is more than three times ML-DSA-44's 2,420 bytes, and signing takes many thousands of hash evaluations.
That makes it the natural choice where signatures are rare, verified often and must last: firmware and software updates, root certificates, long-term archives. It is also the hedge in a portfolio. If a structural attack on lattices ever lands, ML-DSA goes with it, and SLH-DSA does not.
Primary sources
- NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (2024)
- D. J. Bernstein, A. Hülsing, S. Kölbl, R. Niederhagen, J. Rijneveld and P. Schwabe, "The SPHINCS+ signature framework", ACM CCS 2019
- A. Hülsing, "W-OTS+: shorter signatures for hash-based signature schemes", AFRICACRYPT 2013
- R. C. Merkle, "A certified digital signature", CRYPTO 1989
- NIST SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes (2020)