next up previous
Next: Our Contributions Up: The BiBa One-Time Signature Previous: The BiBa One-Time Signature

Introduction

For the past 25 years researchers have created and refined digital signature schemes using one-way functions without trapdoors [2, 5, 9, 10, 13, 14, 18, 23]. These signature schemes are efficient for signature generation and verification, but the signatures are too large for many applications. We propose the BiBa signature, a new approach for signatures based on one-way functions without trapdoor. The signature size of our scheme is much smaller than most previous signatures based on one-way functions; and the verification is also more efficient. However, our public keys are larger than most previous systems, and the time to generate signatures is also higher.

Our new signature scheme immediately yields important new applications. In particular, we extend the BiBa signature scheme to design a new protocol for authenticating broadcasts, such as streaming information broadcast over the Internet. Many applications need to authenticate broadcast data, i.e. verify the data origin. The main challenges to design an efficient broadcast authentication protocol are:

Researchers proposed a number of schemes for broadcast authentication [4, 6, 16, 17, 23, 25]. Unfortunately most previously proposed systems [6, 16, 17, 23, 25] cannot simultaneously support both real-time authentication and perfect robustness to packet loss. One approach that supports both real-time authentication and robustness to packet loss [4] does not scale well to large number of receivers, as the size of authentication information increases as the number of receivers increases. Using a new construction, we design the BiBa broadcast authentication protocol from the BiBa signature scheme, that satisfies all the above desired properties, except that the sender overhead to generate the authentication information is in general higher than for previous approaches (although it can be parallelized). In addition, the BiBa broadcast authentication protocol requires that the sender and receiver are weakly time synchronized.gif

Similar to the MicroMint payment scheme by Rivest and Shamir [21], the security of the BiBa signature comes from the difficulty of finding k-way collisions for a one-way function. The main difference, however, is the security assumption: MicroMint assumes that the bank has more computational resources than an adversary, but BiBa enjoys exponentially increasing security such that it is secure even if the signer only has modest computation resources.gif


next up previous
Next: Our Contributions Up: The BiBa One-Time Signature Previous: The BiBa One-Time Signature

Adrian Perrig
Mon Nov 26 15:18:51 PST 2001