04 — Few-Time Signatures (FORS)

The Problem WOTS+ Leaves

WOTS+ signs one message securely. To sign $2^h$ messages, we need a Merkle tree of $2^h$ WOTS+ keys. But what if we want a simpler structure without managing thousands of WOTS+ keys?

FORS (Forest of Random Subsets) provides a middle ground: sign a few messages with one public key, using a different approach.

How FORS Works

Setup

1. Choose parameters:

   • $k$ = number of subsets (e.g., 33)
   • $a$ = tree height per subset (e.g., 14)
   • $t = 2^a$ = number of leaves per subset

2. Generate $k$ independent Merkle trees, each with $t$ random leaf values:

Tree 1          Tree 2          ...     Tree k
Root_1          Root_2                  Root_k
  |               |                       |
 / \             / \                     / \
L L ...         L L ...                 L L ...
(2^a leaves)    (2^a leaves)            (2^a leaves)

3. The public key is the hash of all tree roots: $pk = Hash(Root_1 || Root_2 || ... || Root_k)$

Signing

1. Hash the message to a $k \times a$-bit digest.
2. Split into $k$ indices: $idx_1, idx_2, ..., idx_k$ (each in $[0, 2^a-1]$).
3. For each tree $i$, select the leaf at index $idx_i$.
4. Include:
   • The $k$ selected leaf values
   • The Merkle path for each selected leaf (to prove it's in the tree)
5. The signature is: $\sigma = (leaf_1, path_1, leaf_2, path_2, ..., leaf_k, path_k)$

Verification

1. Hash the message to get the same $k$ indices.
2. For each tree $i$:
   • Use $leaf_i$ and $path_i$ to compute $Root_i'$
3. Check: $Hash(Root_1' || Root_2' || ... || Root_k') == pk$

Security Analysis

FORS is secure for a few signatures because:

First signature: Reveals $k$ random leaves (one from each tree). Second signature: Reveals $k$ more random leaves.

The probability of collision (same index chosen twice in the same tree):

$\displaystyle P(\text{collision}) = 1 - (1 - \frac{1}{t})^{k \cdot \text{signatures}}$

For $t = 2^{14} = 16,384$ and $k = 33$:

• After 1 signature: negligible collision risk
• After 10 signatures: still very low
• After 100 signatures: ~2% collision risk (too high)

That's why FORS is "few-time" — safe for a small number of signatures, unsafe for many.

FORS Parameters

FORS vs. WOTS+

FORS in SLH-DSA

SLH-DSA uses FORS for the bottom layer of signatures (the actual message signing), and WOTS+ for the upper layers (signing the FORS public keys and tree navigation).

Message
   |
   v
FORS signature (few-time, large)
   |
   v
WOTS+ signatures (one-time, chain up the tree)
   |
   v
Hypertree root (long-term public key)

This hybrid approach balances security and efficiency.

Resources

• Bernstein et al., "SPHINCS+ — Submission to the NIST post-quantum project" (2020), v3.1
• NIST FIPS 205, Section 6: FORS Algorithm
• Hülsing et al., "XMSS-T: Hash-based signatures with tight security" (2017), PQCrypto