Sign up ×
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.

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

1 Answer 1

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