The BiBa Signature Scheme

 

We now describe the BiBa signature scheme in more detail. To sign message $m$ the signer computes the $m$₃ bit long hash $h=H(m|c)$, where $c$ is a counter value that the signer increments if it cannot find a signature. The signer has $t$ SEALs (each is $m$₂ bits long), and maps them with the hash function $G$_h into $n$ bins. Any $k$-way collision of SEALs forms the signature.

Verification is straightforward. We assume that the verifier knows the BiBa parameters $k$ and $n$, the hash function $H$, and the hash function family $G$.

Assume the verifier receives message $m$ and BiBa signature $$x₁, &ldots;, Sx_k, c. First, the verifier verifies that all $k$ SEALs are distinct and authentic. Next, the verifier computes $h=H(m|c)$, and accepts the signature if all $G$_h(Sx_i) (for $1\; \le i\; \le k$) are equal.