One-Round BiBa is as secure as Multi-Round BiBa

     

We illustrate a multi-round scheme with a concrete example. Figure 7 illustrates this approach for two rounds. In the first round, we look for two-way collisions under a hash function $G$_h. The indices of the bins that have at least a two-way collision in the first round are used as balls in the second round, and a three-way collision is required under $Ĝ$_h. The indices that participate in the three-way collision in the second round and the SEALs necessary to verify that each index corresponds to a bin with the two-way collision in the first round, form the BiBa signature: $$x₁, &ldots;, Sx₆.

  
Figure 7: Signature scheme with two rounds

To verify the BiBa signature $$x₁, Sx₂, Sx₃, Sx₄, Sx₅, Sx₆ of message $m$ (with $h=H(m)$), the verifier verifies the following conditions:

1. All six SEALS $S$_i are distinct and authentic
2. Throwing all $6$ SEALs into $n$₁ bins results in $3$ two-way collisions in bins with indices $b$₁, b₂, b₃. These indices form a three-way collision under $Ĝ$: $Ĝ$_h(b₁) = Ĝ_h(b₂) = Ĝ_h(b₃).

We now sketch a proof that a one-round BiBa signature scheme are as good as a multi-round signature scheme. Please consult the full version of this paper for an extended proof.
 

            

The proof is in the full version of this paper.