The Signature Budget: How FORS Turns Two-to-the-Sixty-Four into a Graceful Slope, and What s and f Really Trade

A stateful hash-based signature has a hard limit: use a one-time key twice and the scheme can be forged. SLH-DSA advertises the opposite, a signer that remembers nothing, and it is tempting to read that as unlimited. It is not. FIPS 205 sizes every parameter set for at most 2 to the power 64 signatures per key, a figure the standard illustrates with a signer producing ten billion signatures every second for more than 58 years. The number is not arbitrary, and it is not a cliff. It falls out of a few-time signature scheme called FORS, a message hash that chooses which FORS key to use, and a probability that grows smoothly with every signature issued. Understanding that probability tells you what the budget really protects, why the two families of parameter sets behave differently near it, and which property of SLH-DSA no signature budget can buy.

What the message digest decides

Signing in FIPS 205 begins with two hashes. A pseudorandom function keyed with the secret SK.prf turns the message and an optional random string into an n-byte randomiser R. Then the message hash H_msg combines R, the public seed, the public root and the message into an m-byte digest. Algorithm 19 of the standard cuts that digest into three pieces: the first part is the message that the bottom FORS key will sign, the second selects which bottom tree of the hypertree is used, and the third selects which leaf of that tree, and therefore which WOTS+ key and which FORS key, signs it.

This arrangement has a consequence that is easy to state and central to everything that follows. The signer does not choose the FORS key; the digest does. Each signature lands on a FORS instance that is, for all practical purposes, uniformly random among 2 to the power h instances, where h is the total hypertree height: 63 for the 128s, 192s sets, 64 for 256s, 66 for 128f and 192f, and 68 for 256f. With q signatures spread over 2 to the power h instances, the average number of signatures per instance is q divided by 2 to the power h, and the number landing on any particular instance follows, to an excellent approximation, a Poisson distribution with that average.

The design also binds the index to the message. SPHINCS, the predecessor, chose the few-time key pseudorandomly but did not let the verifier check how, which allowed a multi-target attack: map a message to its positions first, then claim whichever instance already had those positions exposed. The SPHINCS+ specification describes how computing the digest and index together from H_msg removes that freedom, because choosing a message now fixes the index. As a bonus the index no longer needs to be carried in the signature.

The randomiser deserves a sentence of its own. In the hedged mode that FIPS 205 makes the default, signing the same message twice draws two different values of R and therefore, almost surely, two different FORS instances; each repetition spends budget. In the deterministic mode, R depends only on the key and the message, so re-signing an identical message lands on the same instance and reveals nothing new. Neither mode changes the analysis below, which counts distinct digests.

FORS: a few-time signature and what each reuse costs

FORS, the forest of random subsets introduced in the SPHINCS+ framework paper, is a few-time signature: it stays secure for a small number of uses and weakens gradually rather than collapsing after the second. A FORS key is k separate Merkle trees, each with t equals 2 to the power a secret leaves. To sign, the FORS message is read as k indices of a bits each, and from tree i the signer reveals the secret at index i together with its authentication path. The k tree roots are compressed into the FORS public key, which the hypertree above then certifies.

Forging a FORS signature on a new message requires knowing the secret at every one of the k positions that message selects, and the only secrets an attacker knows are those already revealed. After an instance has signed gamma times, each of its trees has at most gamma revealed leaves, so a random new message is fully covered with probability about the k-th power of one minus the chance that a single position has never been revealed. The SPHINCS+ designers chose FORS over its predecessor HORST precisely because HORST drew all k indices from one shared pool of secrets, which created weak messages that needed very few secrets; separate trees per index remove that shortcut.

The table below, our own evaluation of that expression, shows how the generic forging cost for a single FORS instance falls as it is reused. Two shapes are visible at once. The 128s instance, with 14 trees of 4,096 leaves, starts lower but descends slowly, still above 140 bits after four uses. The 128f instance, with 33 trees of only 64 leaves, starts higher but falls fast, below 103 bits after eight uses. The limited-use draft set added in 2026 is flatter still: 6 trees of 2 to the power 24 leaves each, designed so that a single instance can be reused many times.

Per-instance numbers are not the security of the scheme, because an attacker cannot choose which instance a new message lands on. They are the ingredients: the scheme's security is an average of these values weighted by how many instances have been used how often.

Where two to the sixty-four comes from

Combine the two ingredients and the budget appears. Section 9.3 of the SPHINCS+ version 3.1 specification defines the property the message hash must have, interleaved target subset resilience, and computes its generic cost exactly: sum, over every possible reuse count gamma, the probability that the target instance has been used gamma times multiplied by the probability that gamma uses cover a new message. A classical attacker who evaluates the hash q-hash times succeeds with probability about q-hash times that sum; the specification's quantum figure squares the query count, so the quantum security in bits is roughly half the classical figure.

The specification gives one checkpoint, which we reproduce: for t equals 2 to the power 14, k equals 22, h equals 64 and 2 to the power 64 signatures, the probability that a new digest falls on already-revealed positions is 2 to the power minus 256.01, with most of the weight coming from instances used between 7 and 13 times. Those are the 256s parameters, so at exactly its budget the 256s set sits at its category-5 strength of 256 bits.

The budget, in other words, is the signature count at which this term reaches the claimed security of the category, given n. Above it the term begins to dominate the bound; below it the bound is limited instead by the 2 to the power 8n cost of attacking the hash outputs themselves. At 2 to the power 64, the evaluated term gives about 134 bits for 128s, 131 for 128f, 194 for 192s, 195 for 192f, and 256 for 256s and 256f, each at or above the nominal 128, 192 or 256.

Why only the bottom of the tree spends the budget

A natural objection: the hypertree above FORS is built from Winternitz one-time signatures, and every SLH-DSA signature uses d of them. If one-time keys break when reused, why do the upper layers not exhaust long before FORS does? The answer is a detail of what those one-time keys sign. A Winternitz key in the hypertree signs either the root of the tree below it or a FORS public key, and those values are fixed by the secret seed. However many times a given upper-layer key is used, it signs the same value every time, and a one-time signature revealed twice on the same message reveals nothing new.

That is why the signature count enters the security bound through exactly one term, the message hash's subset resilience, and why the hypertree contributes only the fixed cost of attacking its hash outputs. It also explains the parameter choice for the tree height h. The height does not protect the hypertree; it sets how many FORS instances the signatures are spread across. Raising h by one halves the average load per instance and costs one more authentication-path node per signature.

The same detail is the one weak point of the construction in a physical setting. The argument depends on each hypertree key always signing the same value. A computation error that made an upper-layer key sign a different value even once would turn a harmless repetition into a genuine one-time-key reuse, which is the opening that fault attacks on the SPHINCS family exploit. The budget analysis assumes a signer that computes correctly; that assumption has to be earned separately in hardware.

Past the limit: a slope, not a cliff

Because the term is a smooth function of the signature count, exceeding the budget lowers security gradually. The figures below, again our evaluation of the published expression, show the classical generic bits contributed by the message-hash term at counts beyond 2 to the power 64. Two extra doublings, to 2 to the power 66, cost each set roughly 17 to 21 bits; reaching 2 to the power 68 costs roughly 38 to 49; by 2 to the power 72 the category-1 sets are far below any acceptable level.

Translate that into operations. FIPS 205's own illustration, ten billion signatures per second for more than 58 years, is the 2 to the power 64 point. Two more doublings would take that same imaginary signer more than two centuries, and exhausting a key to the point where the f sets fall below 90 bits would take roughly a thousand years at that rate. For any real signer of model releases, packages or agent tool manifests, the FIPS 205 budget is an engineering non-issue; its value lies in knowing that the boundary is soft, so an accounting error never becomes a sudden break.

The slope matters much more for parameter sets designed with a smaller budget. NIST's April 2026 draft of SP 800-230 proposes sets with a 2 to the power 24 limit, and the same calculation shows they too degrade gradually: about 108 bits at 2 to the power 28 and 84 bits at 2 to the power 32 for the category-1 draft set. Whether a slope that steep is acceptable is a deployment decision, not a property of the algorithm.

What s and f really trade

The small and fast families are usually explained by their headline costs: s signatures are smaller and slower to make, f signatures are larger and faster. The budget analysis shows a deeper difference. The two families reach the same category at 2 to the power 64 by opposite strategies. The s sets use h equals 63 or 64, so at the budget the average FORS instance has been used once or twice, and they compensate with strong instances whose trees have thousands of leaves. The f sets use h equals 66 or 68, so at the budget most instances have never been used at all, and they can afford weak instances with 64 to 512 leaves per tree because reuse is rare.

At the 128-bit level the contrast is stark. At 2 to the power 64 signatures, about 59 percent of the 128s instances have been used at least twice, while only about 3 percent of the 128f instances have. The s family absorbs reuse; the f family avoids it. That is why, past the limit, the f sets lose bits faster: as the count grows, reuse stops being rare, and the weak f instances meet it unprepared.

The headline costs come from the same parameters. Signature size, from Figure 17 of FIPS 205, is n bytes for R, k times one plus a times n bytes for FORS, and h plus d times len times n bytes for the hypertree; for 128s that is 16 plus 2,912 plus 4,928, or 7,856 bytes, and for 128f 16 plus 3,696 plus 13,376, or 17,088 bytes. The f sets pay in hypertree layers: 22 Winternitz signatures per f signature against 7 for s. Signing cost is dominated by building each layer's tree, 7 trees of 512 leaves for 128s against 22 trees of 8 leaves for 128f, which is why f signs faster. The same layer count means an f verifier completes 22 Winternitz signatures where an s verifier completes 7, so f signatures are not only larger but also more work to check, a point worth remembering for constrained verifiers.

The published sets are also deliberately not the extremes of what the formulas allow. The SPHINCS+ version 3.1 specification explains that its parameter sets came from a search script over the whole design space, and that the authors chose non-extreme points with signing times of at most a few seconds in their unoptimised implementation. Optimising for size alone at the 256-bit level would give signatures of about 15 kilobytes, roughly half of 256s, but would take more than 20 minutes to sign on their benchmark platform. The twelve standard sets are therefore a negotiated middle, and other points on the same curve, including much smaller budgets, are a matter of choosing different trade-offs rather than different mathematics.

None of this changes the category claim at the budget. It changes how forgiving each family is of an accounting error, and it reframes the choice: an s set is the conservative pick when the true signature count is uncertain, and an f set is the pick when signing latency dominates and the count is comfortably bounded.

Why the index must be verifiable

The averaging argument hides a sharp edge. Instances are not reused evenly. With 2 to the power 63 instances and an average of two uses each, as for 128s at its budget, the Poisson tail means some instances have been used about 26 times. From the per-instance table, a 128s instance used 26 times offers only on the order of a hundred bits against a covering attack.

If an attacker could choose which instance to attack, the scheme's security would be set by its most-used instance rather than its average, and the budget would be far lower. That is exactly the multi-target weakness the SPHINCS+ specification describes in the original SPHINCS, where the index was pseudorandom but unverifiable: map a message to its positions, then claim whichever instance already exposed them. Deriving the index and the FORS message together from H_msg, and recomputing both during verification, takes that choice away. A new message picks its own instance, and the attacker inherits the average.

The lesson for implementers is narrow but absolute: the verifier must recompute the tree and leaf indices from the digest and use them; an implementation that trusted an index supplied alongside the signature, or a protocol that allowed one to be substituted, would reopen the gap that FORS index binding closed.

When the signer is the adversary

The signature budget protects against outsiders forging new messages. It says nothing about a different question that matters for provenance: can the key holder produce one signature that is valid for two different messages? FIPS 205 addresses this directly. This property, called message-bound signatures, is not part of the existential-unforgeability definition used to assign categories, and SLH-DSA does not fully provide it: the key owner can choose R freely and search for two messages with the same H_msg digest under the same randomiser and key, after which one signature verifies for both.

The cost of that search is a birthday collision on the digest bits that matter, which FIPS 205 puts at about 2 to the power of half of h plus k times a evaluations. For 128s that is about 2 to the power 115.5, for 192s about 2 to the power 150.5, and for 256s about 2 to the power 186. The standard notes that this falls below the claimed category for every parameter set except 128f and its SHAKE twin, where the exponent is 132. These are still astronomically large numbers, but they are below the category labels a reader might assume apply.

FIPS 205 offers two remedies: take the collision cost into account when choosing a parameter set, or apply a transformation such as BUFF, from the work of Cremers, Duzlu, Fiedler, Janson and Fischlin, that binds the signature to the message by construction. For a model publisher the practical question is whether any downstream process treats the signature itself as the identity of the artefact. Transparency logs, deduplication caches and dispute processes should key on the artefact's own cryptographic digest and record it alongside the signature, so that a hypothetical colliding pair could never be presented as one signed object.

Why this matters for agents and model supply chains

For the signing workloads around AI agents, the budget analysis sorts concerns into three bins. The first bin is volume. A release key that signs model weights, a registry key that signs tool manifests, or a service key that signs agent actions cannot plausibly approach 2 to the power 64 signatures, even across many replicas sharing one key, so the FIPS 205 sets need no signature counter for security. A count is still good hygiene for detecting a stolen key, but it is not a correctness condition, unlike the state of LMS or XMSS.

The second bin is choice of family. When the true count is uncertain, for example a key embedded in many signing services, an s set fails more gracefully; when latency dominates and the count is small and known, an f set is defensible, at the price of larger signatures and more verification work on every agent that checks them. The third bin is binding. Provenance systems for models and agent tools should never let a signature stand in for the identity of what was signed, because the signer-side collision bound is below the nominal category for most sets.

A word on the limits of this analysis. The tables are generic classical estimates from one term of the published bound, evaluated by us with a Poisson approximation that reproduces the specification's checkpoint; they assume an ideal hash and say nothing about implementation attacks. The scheme's overall level is also capped by the 2 to the power 8n cost of attacking hash outputs, and the quantum figures are roughly half the classical ones under the specification's model. None of the numbers is a measurement of a real attack.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

function coverage_bits(h, a, k, log2_q):
    t = 2 ** a
    lam = 2 ** (log2_q - h)          # average uses per FORS instance
    total = 0
    for gamma in 1 .. upper_tail(lam):
        p_load = poisson(lam, gamma)  # chance the target instance has gamma uses
        p_cover = (1 - (1 - 1/t) ** gamma) ** k
        total += p_load * p_cover
    return -log2(total)              # classical generic bits from this term

# check: coverage_bits(64, 14, 22, 64) should be about 256 (spec checkpoint)
for set in parameter_sets:
    report set.name, [coverage_bits(set.h, set.a, set.k, x) for x in (64, 66, 68)]
    report 'overall cap', 8 * set.n

key: model-release-root-2026
algorithm: SLH-DSA-SHA2-128s
claimed_budget: 2 to the 64 signatures (FIPS 205)
expected_signatures_lifetime: under one million
margin_basis: SPHINCS+ v3.1 coverage term, generic classical
signing_mode: hedged
verifier_requirements:
  recompute_fors_index: true
provenance:
  record_artefact_digest_with_signature: true
  message_binding_transform: optional

Glossary

Signature budget

The maximum number of signatures per key for which a parameter set is claimed to meet its security category; 2 to the power 64 for FIPS 205 sets.

FORS

Forest of random subsets: a few-time signature of k Merkle trees whose message selects one revealed leaf per tree.

Few-time signature

A signature scheme that remains secure for a small number of uses and weakens gradually with further reuse.

Coverage probability

The chance that a new message's FORS positions are all among those already revealed by earlier signatures.

Interleaved target subset resilience

The property of H_msg that bounds an attacker's chance of finding a message whose selected positions are all already covered.

Verifiable index selection

Deriving the FORS instance index from the same message hash as the FORS message, so it can be recomputed and cannot be chosen.

Message-bound signature

A signature that cannot be valid for two different messages even when the key holder constructs both.

BUFF transformation

A generic construction that adds beyond-unforgeability properties, including message binding, to a signature scheme.

s and f parameter sets

FIPS 205 sets optimised for relatively small signatures (s) or relatively fast signature generation (f) at the same category.

References

1. NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (2024)
2. SPHINCS+ Submission to the NIST post-quantum project, specification v3.1 (2022)
3. Bernstein et al., The SPHINCS+ Signature Framework (ACM CCS 2019)
4. NIST SP 800-230 ipd, Additional SLH-DSA Parameter Sets for Limited-Signature Use Cases (2026)
5. Fluhrer and Dang, Smaller Sphincs+ (2024)
6. Kolbl and Philipoom, A note on SPHINCS+ parameter sets (2022)
7. Cremers, Duzlu, Fiedler, Janson and Fischlin, BUFFing Signature Schemes Beyond Unforgeability and the Case of Post-Quantum Signatures (IEEE S&P 2021)