Adrian Perrig
University of California, Berkeley
Digital Fountain
perrig@cs.berkeley.edu
We introduce the BiBa signature scheme, a new signature construction that uses one-way functions without trapdoors. BiBa features a low verification overhead and a relatively small signature size. In comparison to other one-way function based signature schemes, BiBa has smaller signatures and is at least twice as fast to verify (which probably makes it one of the fastest signature scheme to date for verification). On the downside, the BiBa public key is large, and the signature generation overhead is higher than previous schemes based on one-way functions without trapdoors (although it can be trivially parallelized).
One of the main challenges of securing broadcast communication is source
authentication, which allows all receivers to verify the origin of the data.
An ideal broadcast authentication protocol should be efficient for the sender
and the receiver, have a small communication overhead, allow the receiver to
authenticate each individual packet, provide perfect robustness to packet
loss, scale to large numbers of receivers, and provide instant authentication
(no buffering of data at the sender or receiver side). We are not aware of any
previous protocol that satisfies all these properties. We present the BiBa
broadcast authentication protocol, a new construction based on the BiBa
signature, that achieves all our desired properties, with the tradeoff that it
requires a moderate computation overhead for the sender to generate the
authentication information, and that it requires loose time synchronization
between the sender and receivers.
Keywords: Broadcast
authentication, source authentication for multicast, one-time signature,
signature based on a one-way function without trapdoor.