I am reading the page 38 in this "Post Quantum Cryptography" book (Equations 8 and 9). My question is, why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? Are there any security notions involved?
9
$\begingroup$
$\endgroup$
7
$\begingroup$
$\endgroup$
$w$ is a parameter that can be freely chosen, to maximize performance. Each element of the signature encodes $w$ bits of the message to be signed, so the larger $w$ is, the fewer elements you need to include in the signature.
If you make $w$ large, then signatures can be shorter; however, the tradeoff is that key generation, signing, and verification run slower. If you make $w$ small, then signatures are longer; however, key generation, signing, and verification run faster. So this is a tradeoff between the size of the signatures vs the running time of the scheme. You can choose $w$ to provide the best tradeoff for your application. The scheme will be secure no matter what value of $w$ you choose.
-
1$\begingroup$ understand, thanks by your reply, and Why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? $\endgroup$ – juaninf Jul 2 '13 at 17:14
4
$\begingroup$
$\endgroup$
Though this question is fairly old, there is still no accepted answer. Hence, let me try to clarify this.
The W-OTS scheme that your talking about was proposed by Ralph Merkle in his 1979 paper as an improved version of the Lamport-Diffie OTS to reduce the size of signatures. Instead of a "per-bit-signature", Merkle proposed to sign multiple Bits at once. He was inspired by Robert Winternitz, hence the name.
$w$ is the number of bits that are signed simultaneously. Applying $F$ $2^{w-1}$ times allows for log($w$) Bits to be signed simultaneously.
Let me use the example from Merkle's paper. To sign 4 Bit strings, you would compute the verification key $F^{15}(x)$, where $x$ is the private key. To sign the number 9 (1001 in binary) you would compute $F^9(x)$. To verify this Signature, one would compute $F^6(F^9(x))$. By this the receiver would know that the sender computed $y$.
0
$\begingroup$
$\endgroup$
I cannot comment on the question, so I will try to answer the question. (correct me if I'm wrong).
The digest of the message is split into bit string $b_i$ of length $w$, so the value of $b_i$ is smaller or equal $2^w-1$.
To compute verification key, $2^w-1$ is minimum number of function evaluations needed (i.e. cannot have negative function evaluation). So any number is bigger than $2^w-1$ will work, but it's redundant.
