The BiBa signature uses the birthday paradox to construct a digital signature scheme from a one-way function without a trapdoor. A BiBa signature is a -way collision of input values under a hash function in the random oracle model. In comparison to previous approaches the BiBa signature offers smaller signature size, and a smaller verification overhead. On the downside, the public key is larger and the signature generation overhead is higher than for previous approaches.
The BiBa one-time signature is particularly useful in settings where the signer can send the public key to the verifier efficiently, or where the verifier is constrained on computation power. Furthermore, the BiBa signature generation enjoys a linear speedup on multiprocessor systems until signature generation and verification only require two sequential hash function evaluations.
Broadcast authentication remains an important problem. As far as we know, no previous protocol could provide perfect robustness to packet loss, instant authentication (without sender- or receiver-side buffering), efficient verification, and scalability to a large number of receivers. We propose a new construction to achieve perfect loss robustness for signature schemes based on one-way functions without trapdoors. By combining our new construction with the BiBa signature scheme, we obtain the BiBa broadcast authentication protocol.