I was reading the HORS One-Time-Signature scheme by Reyzin & Rezyin, but I could not understand how they derived their security equation $(rk⁄t)^k$. I understand that the total number of balls is $t$, and each time a signer signs his message, he reveals $k$ different balls. The attacker at this point and after one signatures, he knows $k$ elements (balls). After $r$ signatures, the attacker at most knows $rk$ out of $t$ elements. Then, why it was raised to power of $k$? and why is the security log of this equation?


1 Answer 1


Here's how it works:

  • After $r$ signatures, he learns, at most, $rk$ balls (actually, that's a maximum; however that is a conservative estimate).

  • Hence, the probability that a random ball has been revealed is $rk/t$

  • Now, he tries to generate a forgery; he picks a message that hasn't been signed, and translates that into $k$ balls. He can generate a forgery if all these balls have been revealed; the probability that a specific ball is $rk/t$; these balls were selected independently, and so that probability that all of them has been revealed is $(rk/t)^k$

So, if the attacker tries to select random messages until he finds one that works, that'd take an expected $((rk/t)^k)^{-1} = 2^{-\log_2 (rk/t)^k}$ tries. We express security levels in terms of powers of 2, and so the "security" of this system would be $-\log_2 (rk/t)^k$

  • $\begingroup$ Thank you very much.. This is really clear now. I am a graduate student and I was struggling with it. Thank you very the explanations. It is very clear now. $\endgroup$
    – Mona
    Commented May 17, 2019 at 0:16

Your Answer

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

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