Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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

share|improve this answer

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

share|improve this answer
understand, thanks by your reply, and Why to compute the verification key $Y$, $f$ is applied $2^w-1$ times? – juaninf Jul 2 '13 at 17:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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