Signature Generation

To sign a message $m$, the signer first computes the hash $h\; =\; H(\; m\; )$. The signer then computes the hash function $G$_h (as we describe at the beginning of this section) to all the SEALs $s$₁, &ldots;, s_t. The signer looks for a two-way collision of two SEALs: $G$_h(s_i) = G_h(s_j), with $s$_i ≠s_j. The pair $s$_i, s_j forms the signature. Figure 1 shows an example. It is now clear why the BiBa acronym stands for Bins and Balls signature: the bins correspond to the range of the hash function $G$_h, and the balls correspond to the SEALs.

  
Figure 1: Basic BiBa scheme

We exploit the asymmetric property that the signer has more SEALs than the adversary, and hence the signer can easily generate the BiBa signature with high probability. On the other hand, an adversary only knows the few disclosed SEALs and hence has a low probability to find a valid BiBa signature.