Our Publications

by Adrian Perrig
Abstract:
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.
Reference:
The BiBa One-Time Signature and Broadcast Authentication Protocol  [bibtex]Adrian Perrig. In Proceedings of ACM Conference on Computer and Communications Security (CCS) 2001.
Bibtex Entry:
@InProceedings{Perrig2001,
  author = 		 {Adrian Perrig},
  title = 		 {The {BiBa} One-Time Signature and Broadcast Authentication Protocol},
  url = {http://www.netsec.ethz.ch/publications/papers/biba.pdf},
  booktitle =	 {Proceedings of ACM Conference on Computer and Communications Security (CCS)},
  year =		 2001,
  pages =        {28--37},
  address =		 {Philadelphia PA, USA},
  month =		 Nov,
  abstract =	 {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.}
}