2
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.