Adrian PerrigWe gratefully
acknowledge funding support for this research. This research was sponsored
in part the United States Postal Service (contract USPS 102592-01-Z-0236),
by the United States Defense Advanced Research Projects Agency (contract
N66001-99-2-8913), by the United States National Science Foundation (grant
FD99-79852), and by Digital Fountain. DARPA Contract N66001-99-2-8913 is
under the supervision of the Space and Naval Warfare Systems Center, San
Diego. This paper represents the opinions of the authors and does not
necessarily represent the opinions or policies, either expressed or implied,
of the United States government, of DARPA, NSF, USPS, any of its agencies,
or of Digital Fountain.
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.