# Winternitz hash based signature signing and verification

In Winternitz hash based signature

There are two functions $f: \{0,1\}^n \to \{0,1 \}^n$, a one way function and $g: \{0,1\}^* \to \{0,1 \}^n$, cryptographic hash function

Key Generation steps

• First $w$ is selected, where $w$ is number of bits signed simultaneously.
• The $t_1$ and $t_2$ is calculated as $t_1 = \lceil \frac{n}{w}\rceil$ and $t_2 = \lceil \frac{\lfloor log_2t_1\rfloor +1+w}{w}\rceil$, $t = t_1 + t_2$
• Signature Key (Private key) is then chosen at random $X = (x_{t-1}, ..,x_0)\in \{0,1 \}^{n, t}$
• Verification key (public key) $Y$ is calculated by applying $f$ function $2^{w} - 1$ times on each bit of $x_i$

Signing steps

• Compute digest of message $d = g(M)$
• Prepend minimum number of zero's to make length of $d$ divisible by $w$

My questions are

How is signature $\sigma$ computed? I am unable to understand from Post Quantum cryptography. Explanation with example would be helpful.

Why there is two functions $f$ and $g$, is there can be only one hashing function. What is the role of function $f$?

https://csrc.nist.gov/csrc/media/events/workshop-on-cryptography-for-emerging-technologies/documents/mcgrew-sigs.pdf

How is signature $$\sigma$$ computed?

Well, you left a few steps out of your signing steps:

Signing steps

• Compute digest of message $$d = g(M)$$
• Prepend minimum number of zero's to make length of $$d$$ divisible by $$w$$

(Note: in practice, the length of $$d$$ is typically already divisible by $$w$$, and so this step usually doesn't do anything; in any case, $$d$$ will be $$t_1$$ digits long after this step)

• Generate an "inverse checksum" of $$d$$; that is, treat $$d$$ as $$t_1$$ digits of length $$w$$ each $$d_0, d_1, ..., d_{t_1 - 1}$$, compute $$k - \Sigma\ d_i$$ for some constant $$k \ge t_1 (w-1)$$, and express that as the $$t_2$$ digits $$d_{t_1}, d_{t_1 + 1 }, ..., d_{t_1 + t_2 -1}$$

• For each $$d_i$$, take $$x_i$$ and apply $$f$$ to it $$d_i$$ times

• The result of these operations on the $$t_1 + t_2$$ digits are concatenated; that's your signature

You asked for an example, here's a toy one; let us assume that $$w=2$$ and $$n = 4$$. Then:

• We have $$t_1 = 2$$ and $$t_2 = 2$$

• We compute $$g(M)$$ as 0111, which is $$\{ 1, 3 \}$$ as expressed as $$w$$-bit digits

• We don't need to prepend any zeros, the length of $$d$$ is already a multiple of $$w$$

• We generate our inverse checksum; we have $$d_0 = 1$$ and $$d_1 = 3$$; we'll use the minimal $$k = 6$$, and so we have $$k - \Sigma \ d_i = 2$$, which we'll encode as $$d_2 = 0$$ and $$d_3 = 2$$

• We compute the Winternitz chain for $$d_0$$; $$d_0 = 1$$, and so this is $$f(x_0)$$; that's the first 2 bits of the signature.

• We compute the Winternitz chain for $$d_1$$; $$d_1 = 3$$, and so this is $$f(f(f(x_1)))$$; that's the second 2 bits of the signature.

• We compute the Winternitz chain for $$d_2$$; $$d_2 = 0$$, and so this is $$x_2$$ (that is, for digits of 0, we give out the private key value); that's the third 2 bits of the signature.

• We compute the Winternitz chain for $$d_3$$; $$d_3 = 2$$, and so this is $$f(f(x_3))$$; that's the last 2 bits of the signature.

Why there is two functions $$f$$ and $$g$$, is there can be only one hashing function. What is the role of function $$f$$?

They, of course, perform different roles; $$g$$ hashes an arbitrary message down to $$n$$ bits; while $$f$$ is a one-way function that is used within the Winternitz chain itself. They are usually (but not always) based on the same hash function; however how the hash function is used is typically optimized for each role separately.

Of course, in practice, we do a few refinements of the above scheme:

• We actually use a different $$f$$ function for every iteration, and for every digit; that's to avoid multi-target attacks

• Our public key really isn't $$(t_1 + t_2)n$$ bits long; typically, there's a final step that combines them into a single $$n$$ bit value.

Knowledge of these refinements is not necessary to understand Winternitz signatures; however you ought to be aware of them if you dig into a real usage.

• x = \begin{bmatrix} 1 & 0 & 0&1 \\ 1&0&1&1 \\ 1&0&1&0 \end{bmatrix} y = \begin{bmatrix} 0&0&1&0\\ 1&1&1&0 \\ 0&1&0&1 \\ \end{bmatrix} $\sigma = (f(x_3),x_2, f(x_1), f^3(x_0)) =$ \begin{bmatrix} 0&0&1&1 \\ 0&0&0&1 \\ 0&0&0&1 \\ \end{bmatrix} where $f(x) = x + 1 \; mod \; 8$ When i calculate $f^3(x_0) = f(f(f(x_0)$ it comes $001$, but here in the this example it comes $110$ – Infinity Nov 5 '17 at 13:42
• Note that x is signature key and y is verification key. It is example from following book page :$39$ example : $3$e-reading.club/bookreader.php/135832/… – Infinity Nov 5 '17 at 13:47
• The example in the book is wrong; the typo'ed the last column of the $\sigma$ matrix. Yes, the authors are well respected; typos happen... – poncho Nov 5 '17 at 18:13
• Is this possible that there is only hash function. That is applied $2^{w-1}$ times. Is there cases where this modified Winternitz scheme is used. – Infinity Nov 11 '17 at 11:59
• 'Is this possible that there is only hash function'; I have no idea what you are asking... – poncho Nov 11 '17 at 15:21

Let's examine a much simpler system, which has the same needs but none of the complicated key generation: the Lamport–Diffie one-time signature scheme.

A public key is a set $2n$ of $n$-bit strings $Y_{i,b}$, for $b \in \{0,1\}$ and $0 \leq i < n$.

A signature under a public key on a message $M$ is a set of $n$-bit strings $X_i$, such that if the $i^\mathit{th}$ bit of the string $g(M) = b_0 b_1 b_2 \dots b_{n-1}$ is $b_i$, then $f(X_i) = Y_{i,b_i}$.

To generate a public key, the signer picks $2n$ $n$-bit strings $X_{i,b}$ uniformly at random as the private key, and reveals $Y_{i,b} = f(X_{i,b})$. To sign a message, the signer simply reveals $X_i = X_{i,b_i}$, where $b_i$ is again the $i^\mathit{th}$ bit of $g(M)$.

Since $f$ is one-way and the $X_{i,b}$ were chosen uniformly at random, nobody can guess $X_{i,b}$ from $Y_{i,b}$.

The function $g$ is necessary to compress a message into a small representative, and consequently either it must be collision-resistant or it must be randomized.

Of course, once you have revealed $X_i = X_{b_i,i}$, everyone knows what it was, so you can't use this to sign another message because now the cat's out of the bag—at least, some of the cat is out of the bag.

A public key is $2n$ bits in this system, and a signature is $n^2$ bits. (We could have different sizes for the images of $f$ and $g$, if you like, making it $2n$ versus, say, $n\cdot m$.) The Winternitz signature scheme saves some space in signatures at the cost of some time in key generation: in the 2-bit case, a signature on a message $M$ is a set of $n/2$ strings $X_i$ such that $$Y_{2i,b_{2i} b_{2i+1}} = f^{2b_{2i} + b_{2i+1}}(X_i);$$ that is, we break the message into two-bit chunks, and use the bit to select how many iterations of $f$ to apply to verify the newly revealed secret.