Security level in HORS signature scheme

Question

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?

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$