# Winternitz Signature in standard model

I am studying the Winternitz signature and I describe its algorithms in the next

W-OTS Key Generation. Select the parameter $w\geq 2$ that is the bit size of the partitions of the message to be signed. Compute the number of partitions

$$t_1 = \Big \lceil \dfrac{r}{w} \Big\rceil,$$ and parameter $$t_2 = \Bigg\lceil \dfrac{\lfloor \log_2 t_1 \rfloor + 1 + w}{w}\Bigg\rceil,$$ The signature key is $X=(x_0, x_1 \cdots, x_{t-1}) \in \{0,1\}^{r,t}$, where the bit-strings $x_i$ with $0 \leq i \leq t-1$ are randomly chosen. The verification key $Y$ is computed by applying ${\mathcal{H}}$ $2^w-1$ times in each bit-string $x_i$ of the signature key, i.e. $Y=(y_{0},\cdots, y_{t-1})$ with $y_i = {\mathcal{H}}^{2^w-1}(x_i)$.

W-OTS Signature Generation. Compute the digest $d$ of message $M$ to be signed using $g$, i.e., $g(M) = d = (d_0, \cdots, d_{r-1})$. Add zeros to $d$ until it is divisible by $w$. The partition of $d$ into $t_1$ $w$-sized parts is $$d = b_0|| b_1|| \cdots || b_{t_1-1}.$$ Note that each element $b_i$ can be transformed into base-$10$ representation and identified with integers $\{0,\cdots, 2^w-1\}$.

Calculate the checksum $$c=\sum_{i=0}^{t_1-1} 2^w - b_i.$$ The maximum number of bits representing $c$ in binary base is $\lfloor \log_2 t_1 \rfloor + w + 1$. Indeed, note that $c = t_1 2^w - \sum_{i=0}^{t_1-1}b_i \leq t_1 2^w$ and the number of bits required to represent $t_1 2^w$ is $\lfloor \log_2 t_1 2^w \rfloor + 1 = \lfloor \log_2 t_1\rfloor + w + 1.$

Similarly, split the binary representation of $c$ into $t_2$ $w$-sized parts, i.e., $$c = c_0|| c_1|| \cdots || c_{t_2-1}.$$ Finally, computing the signature as $$\sigma_{\text{W-OTS}} = (\sigma_0,\cdots,\sigma_{t-1})=({\mathcal{H}}^{b_0}(x_0),\cdots,{\mathcal{H}}^{b_{t_1-1}}(x_{t_1-1}),{\mathcal{H}}^{c_0}(x_{t_1}),\cdots, {\mathcal{H}}^{c_{t_2-1}}(x_{t-1})).$$

W-OTS Verification. To verify the signature $\sigma_{\text{W-OTS}}$ of the message $M$, compute the values $b_i$ and $c_i$ in the same way as above described, then compute $$y'=({\mathcal{H}}^{2^w-1-b_0}(\sigma_0),\cdots,{\mathcal{H}}^{{2^w-1-b_{t_1-1}}}(\sigma_{t_1-1}),{\mathcal{H}}^{2^w-1-c_0}(\sigma_{t_1}),\cdots,{\mathcal{H}}^{2^w-1-c_{t_2-1}}(\sigma_{t-1})),$$ and compare $y'$ with $Y$. The signature is valid only if $y'_i=y_i$, $\forall i$. \

I need to understand why this present resistence against adaptative chosen message attack. According my knowledge the adaptative chosen message attack works as follow: an attacker can choose a message on which he learns a signature. Afterwards that attacker can choose the message he wants to forge a signature for. This is called the standard model for secure signatures.

My question is why winternitz signature is secure in the standard model? I make this question because using the fact that

"an attacker can choose a message on which he learns a signature"


an attacker can choose the message 00000..0000 and then He learn $\mathcal{H}(x_i)$ for $i \leq t_1$. With these value he can obtain all next values of the form $\mathcal{H}^v(x_i)$, that is he can forge partially any signature because each $\sigma_i$ his obtained using that form.

If he gets the signature for the message 00000..00000, then the checksum will be $t_1 2^w$. For any other message, the checksum will be smaller, and hence the there will be at least one digit $i$ within the checksum for which the $c_i$ digit with value $v$ for the signed message will be larger than the corresponding digit for the new message. The attacker does not know the $\mathcal{H}^{v-1}(x_{i+t_1})$ preimage for that digit, and hence he is unable to forge the signature.

That is the idea behind Winternitz; for any two messages $M_0$ and $M_1$, then either there will be a digit within $M_1$ which is smaller than the corresponding digit within $M_0$, or there will be a digit within the checksum for $M_1$ which is smaller than the corresponding digit within the checksum of $M_0$