# Security level in HORS signature scheme

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?

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

• 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.
– Mona
May 17, 2019 at 0:16