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

https://www.e-reading.club/bookreader.php/135832/Post_Quantum_Cryptography.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 &quot;inverse checksum&quot; 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.