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)

• Have a secret key $x$ and apply $H$ repeatedly $w$ times to form the public key, for example $pk = H^{w}(x)$ where $w=16$.
• where $H^w = H(H(H(\cdots(H(x))))$ denotes $H$ applied $w$ times. We call this a hash chain.
• This allows us to sign $\log_2(16) = 4$ bits of information instead of just one with a single key value.
• To create a signature, split the message digest to be signed into blocks of 4 bits and interpret each block of 4 bits as an integer in the range $[0,15]$.
• To sign the 4 bit message $1001$ (decimal 9), reveal $H^9(x)$.
• To verify, compute $H^7(H^9(x)) = H^{16}(x)$ and check this equals the published value of $H^{16}(x)$.
• More generally, given a message integer $m$ in the range $[0,w-1]$, reveal $H^{m}(x)$ as its signature.
• To verify, show that $H^{w-m}(H^{m}(x)) = H^w(x)$.

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

• Your private key is $x_0, x_1, x_2, \ldots, x_{63}$
• Your public key is $H^{16}(x_0), H^{16}(x_1), H^{16}(x_2), \ldots, H^{16}(x_{63})$
• Compute a 256-bit digest of the message $M$ to-be-signed, $md = \text{SHA-256}(M)$.
• Split the 256-bit $md$ into 64 four-bit blocks and interpret each block as an index integer $m_i$ in the range $[0,15]$
• $md = m_0, m_1, \ldots m_i, \ldots m_{63}$; $0 \leq m_i < 16$
• For each $m_i$, reveal $H^{m_i}(x)$ as its signature

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

## Winternitz parameter

• The value of $w$ is called the Winternitz parameter.
• We don't have to use $w=16$, we can use other convenient powers of two such as 4 or 256.
• $w$ is usually selected from the set $\{4,16,256\}$ giving convenient bit lengths of $\log_2(w)$ $\{2,4,8\}$, respectively.
• be aware that some authors use $w$ to denote the number of bits, so the range of integers becomes $[0, 2^w-1]$.
• Choosing a value for $w$ is a trade off between a shorter signature and increased processing time. Its value has no effect on the security of the scheme.

## A problem with Winternitz

• Since $F^9(x)$ is public, an attacker could compute $F^{10}(x)$ and claim that the signed 4-bit message was 1010 (decimal 10) rather than 1001.
• More generally, if an attacker can find a message digest where each index value is greater than the original, they can forge a signature over the new message.
• To fix, we append a checksum to the message digest before signing.
• If the digest has length $n$, the checksum is typically of length of the order $\log_2(n)$.

## 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];
}

• The checksum is converted to a bit string of length 12 bits, split into 3 x 4-bit blocks to give 3 more index integers, which are appended to the 64 integers from the message digest.
• The signature is now computed over these 67 integers instead of 64. Note that we now need a key of 67 values.
• Remember that a forgery is only possible if we can find a new message digest with every index value greater than the original.
• The checksum computed here ensures that if such a message digest exists, then the checksum will produce at least one index less than the original, which cannot be forged.
• We will see an example of this later when we compute the The Hyper Tree Signature.

## 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 >>