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:

• Efficient generation and verification. The generation and verification overhead for the authentication information should be small. It is important that the verification overhead is small, since a large number of receivers need to verify the authentication information, and some receivers might have restricted computation power.
• Real-time/instant authentication. Many applications such as stock quote broadcasts require real-time data authentication. Hence, neither the sender nor the receiver should buffer data messages before sending or verification.
• Individual message authentication. The receiver can authenticate each individual message it receives.
• Robustness to packet loss. Internet broadcasts can encounter high packet loss. In many broadcast applications, lost packets are not retransmitted. Hence the authentication protocol should tolerate high levels of packet loss.
• Scalability. Broadcast applications have a potentially large number of receivers. The authentication information should be independent of the number of receivers.
• Small size of authentication information. Since the receiver authenticates individual messages instantly, each message carries authentication information, hence a viable scheme should have a low communication overhead.

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.

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.