DI Management Home > Cryptography > SPHINCS+ > Winternitz One-Time Signature (WOTS)

Winternitz One-Time Signature (WOTS)


The Winternitz One-Time Signature (WOTS) was proposed by Winternitz in 1979, shortly before the publication of Lamport's paper. It is described by Merkle [MER79].

Winternitz improvement (WOTS)
Winternitz parameter
A problem with Winternitz
Adding a checksum to WOTS
WOTS+

Winternitz improvement (WOTS)


So, to use a naive Winternitz OTS scheme using SHA-256 with $w=16$, we do the following


An example with $w = 16$ and a message digest of 256 bits.

Example Winternitz scheme

Winternitz parameter

A problem with Winternitz

Adding a checksum to WOTS

Here is a way to compute a checksum, as used in SPHINCS+. For our example above, len_1 = 64 and the length of the checksum is 12 bits.

// Compute checksum for msg of len_1 w-bit integers
csum = 0;
for ( i = 0; i < len_1; i++ ) {
   csum = csum + w - 1 - msg[i];
}

WOTS+

WOTS+ is an improvement over WOTS designed to prevent certain attacks. [WOTSPLUS]

The idea is that instead of just using the plain hash function $H$ each time in the hash chain, a different chaining function is used every time derived from a "family" of keyed hash functions. By family of hash functions it means use a keyed hash function with a "tweak". This ensures domain separation between each member of the hash function family.

A tweakable hash function takes public parameters P and context information in form of a tweak T in addition to the message input. The public parameters can be thought of as a function key or index. The tweak can be interpreted as a nonce.

F = H(PUBLICKEY || NONCE || msg[i])

In practice, this just means that the input to the hash function is distinct each time it is called.

In SPHINCS+, the function F is defined as

F(PK.seed, ADRS, X) = Hash(PK.seed || ADRS || X)
where PK.seed is a public seed, ADRS is an address in the virtual tree structure of SPHINCS+, and X is the input string.

In plain WOTS, where $pk=H^w(x)$, we can define a chaining function $C$ recursively as

C[i] = H(C[i-1]),  C[0] = X

so $C[w] = H^w(x)$. This uses the same H function for each iteration.

In WOTS+, the chaining function $C$ is defined recursively using the tweakable hash function $F$

C[i] = F(PK.seed, ADRS[i], C[i-1]),   C[0] = X

where ADRS[i] includes the counter, $i$.

Domain separation is used to allow the use of the same hash function in different situations (domains). By adding a domain separator that is different each time (PK.seed||ADRS[i]) you are effectively using a different hash function each time you hash msg which ensures a different result even if msg[i] repeats.

<< previous: One-time signature (OTS) scheme Contents next: Merkle Tree >>

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 25 November 2023.