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. Adrian Perrig. In Proceedings of the 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 = {/publications/papers/biba.pdf},
    booktitle =    {Proceedings of the 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.}
}