Security of This Approach

Assume the signer has $t$ SEALs and the range of the hash function $G$_h is $[0,n-1]$. Given a message $m$, the probability of finding a BiBa signature is equal to the probability of finding at least one two-way collision, i.e. at least two balls end up in the same bin, when throwing $t$ balls uniformly randomly into $n$ bins. The probability of at least one collision $P$_C is easy to compute:

$P$_C = 1 - ∏_i=1^t-1{n-in} ≈1 - e^{t(t+1)2n}

Figure 2 shows the probability of at least one collision when throwing $t$ balls into $762460$ bins.

The security of the BiBa signature comes from the fact that the adversary has few SEALs and hence has a small probability to find a collision. For example, if the signer has $1200$ SEALs, as marked with the letter A in Figure 2, it has a $61\%$ probability of finding a signature after one try (one two-way collision after throwing $1200$ balls into $762460$ bins) for a given a message. If we assume that an adversary only knows $10$ SEALs (which it learned from $5$ BiBa signatures), it has a $2-13.9$ probability to find a collision (forge a signature) after one try. Figure 2 shows the adversary's probability, marked with the letter B.