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?


$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

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$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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