03 — One-Time Signatures (WOTS+)

The Core Idea

A one-time signature (OTS) key can sign exactly one message. Reuse it, and an attacker can forge signatures. This seems like a terrible limitation — but with Merkle trees (next article), we can manage millions of OTS keys efficiently.

Winternitz OTS: The Basic Version

Setup

1. Generate $n$ random secret values: $sk_1, sk_2, ..., sk_n$

2. Compute public values by hashing each secret many times:

   $\displaystyle pk_i = H^{w-1}(sk_i)$

   Where $H^k$ means "apply hash $k$ times" and $w$ is the Winternitz parameter (e.g., $w=16$).

Signing

1. Hash the message to get an $n$-byte digest: $d = Hash(message)$
2. Split $d$ into $n$ chunks of $ext{log}_2(w)$ bits each
3. For each chunk $i$ with value $b_i \in [0, w-1]$:
   • Compute signature element: $\sigma_i = H^{b_i}(sk_i)$
4. Output signature: $\sigma = (\sigma_1, \sigma_2, ..., \sigma_n)$

Verification

1. Hash the message to get $d$, split into chunks $b_i$
2. For each signature element:
   • Compute $pk_i' = H^{w-1-b_i}(\sigma_i)$
3. Check: does $(pk_1', pk_2', ..., pk_n')$ match the public key?

Why It Works

If the signer is honest, $\sigma_i = H^{b_i}(sk_i)$, so:

$\displaystyle H^{w-1-b_i}(\sigma_i) = H^{w-1-b_i}(H^{b_i}(sk_i)) = H^{w-1}(sk_i) = pk_i$

If the signer is cheating, they don't know $sk_i$, so they can't compute $H^{b_i}(sk_i)$ for arbitrary $b_i$.

WOTS+ (The Improved Version)

The original WOTS has a weakness: different messages produce related signatures. WOTS+ fixes this with two improvements:

1. Bitmask XOR

Before each hash, XOR with a random bitmask:

$\displaystyle H'(x) = H(x \oplus r)$

Where $r$ is a public random value. This prevents multi-target attacks.

2. Checksum

A checksum is added to prevent signature forgery by increasing chunk values:

Message chunks: b_1, b_2, ..., b_n
Checksum: C = sum(w - 1 - b_i) for all i
Split C into additional checksum chunks
Signature includes both message chunks AND checksum chunks

Why it helps: If an attacker tries to decrease some $b_i$ (to create a "shorter" hash chain), the checksum $C$ increases, requiring them to increase other values. The total sum is fixed, so any change is detectable.

WOTS+ Parameters and Sizes

The One-Time Property

Why can you only sign once?

After signing message $M$ with chunks $b_i$, the signature reveals:

$\displaystyle \sigma_i = H^{b_i}(sk_i)$

If you sign a second message $M'$ with chunks $b_i'$, you reveal:

$\displaystyle \sigma_i' = H^{b_i'}(sk_i)$

An attacker now has two points on the same hash chain:

• $\sigma_i = H^{b_i}(sk_i)$ at position $b_i$
• $\sigma_i' = H^{b_i'}(sk_i)$ at position $b_i'$

If $b_i < b_i'$, the attacker can compute:

$\displaystyle H^{b_i' - b_i}(\sigma_i) = H^{b_i'}(sk_i) = \sigma_i'$

But more importantly, if the attacker wants to forge a message with chunks $b_i''$ where $b_i'' < \min(b_i, b_i')$, they can compute:

$\displaystyle H^{b_i''}(sk_i)$

from either starting point! By combining information from multiple signatures, the attacker can sign any message whose chunks are less than or equal to the minimum values seen across all signatures.

One signature = limited leakage. Many signatures = complete compromise.

From OTS to Many Signatures: Merkle Trees

WOTS+ alone signs one message. To sign many messages, we use Merkle trees to manage many WOTS+ keys.

See: 02 — Merkle Trees and 05 — The Hypertree.

Resources

• Buchmann et al., "XMSS — A practical forward secure signature scheme based on minimal security assumptions" (2011)
• Hülsing, "W-OTS+ — Shorter signatures for hash-based signature schemes" (2013), AFRICACRYPT
• NIST FIPS 205, Section 5: WOTS+ Algorithm