The BiBa one-time signature and broadcast authentication protocol

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.

REFERENCES

• 1: Mihir Bellare , Phillip Rogaway, Collision-Resistant Hashing: Towards Making UOWHFs Practical, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.470-484, August 17-21, 1997
• 2: Daniel Bleichenbacher , Ueli M. Maurer, Directed Acyclic Graphs, One-way Functions and Digital Signatures, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.75-82, August 21-25, 1994
• 3: G.Brassard,editor.Advances in Cryptology - CRYPTO '89 ,number 435 in Lecture Notes in Computer Science,Santa Barbara,CA,USA,1990.
• 4: R.Canetti,J.Garay,G.Itkis,D.Micciancio, M.Naor,and B.Pinkas.Multicast security:A taxonomy and some e .cient constructions.In INFOCOMM '99 ,Mar.1999.
• 5: Shimon Even , Oded Goldreich , Silvio Micali, On-line/off-line digital signatures, Proceedings on Advances in cryptology, p.263-275, July 1989, Santa Barbara, California, United States
• 6: Rosario Gennaro , Pankaj Rohatgi, How to Sign Digital Streams, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.180-197, August 17-21, 1997
• 7: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 8: N.Haller.The S/Key one-time password system.In D.N.G.Chair)andR.S.P.Chair),editors, Symposium on Network and Distributed Systems Security ,San Diego,California,Feb.1994.
• 9: L.Lamport.Discussion with Whit .eld Di .e. http://research.compaq.com/SRC/personal/ lamport/pubs/pubs.html#dig-sig 1975.
• 10: L.Lamport.Constructing digital signatures from a one-way function.Technical Report SRI-CSL-98,SRI International Computer Science Laboratory,Oct. 1979.
• 11: Leslie Lamport, Password authentication with insecure communication, Communications of the ACM, v.24 n.11, p.770-772, Nov. 1981 [doi>10.1145/358790.358797]
• 12: R.Merkle.Protocols for public key cryptosystems.In Proceedings of the IEEE Symposium on Research in Security and Privacy ,Oakland,CA,Apr.1980.
• 13: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 14: Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
• 15: Nessie:New European schemes for signatures, integrity,and encryption. http://www.cryptonessie.org 1999.
• 16: A.Perrig,R.Canetti,D.Song,and D.Tygar. E .cient and secure source authentication for ulticast.In Symposium on Network and Distributed Systems Security (NDSS 2001),SanDiego,CA,Feb. 2001.Internet Society.
• 17: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 18: M.O.Rabin.Digitalized signatures.In R.A.DeMillo, D.P.Dobkin,A.K.Jones,and R.J.Lipton,editors, Foundations of Secure Computation ,pages 155 -168. Academic Press,1978.
• 19: Ron Rivest.The MD5 message-digest algorithm. Internet Request for Comment RFC 1321,Internet Engineering Task Force,April 1992.
• 20: Ron Rivest.The RC5 encryption algorithm.In Anderson,editor,Proceedings of the 1st International Workshop on Fast Software Encryption ,volume 809 of Le ture Notes in Computer Science ,pages 86 -96, 1994.Springer-Verlag,Berlin Germany.
• 21: Ronald L. Rivest , Adi Shamir, PayWord and MicroMint: Two Simple Micropayment Schemes, Proceedings of the International Workshop on Security Protocols, p.69-87, April 10-12, 1996
• 22: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 23: Pankaj Rohatgi, A compact and fast hybrid signature scheme for multicast packet authentication, Proceedings of the 6th ACM conference on Computer and communications security, p.93-100, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319722]
• 24: R.von Mises.~ber Aufteilungs-und Besetzungswahrscheinlichkeiten.Revue de la Faculte des Sciences de l'Universite d'Istanbul ,4:145 -163, 1939.
• 25: C.K.Wong and S.S.Lam.Digital signatures for flows and ulticasts.In IEEE ICNP '98 ,1998.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Electronic data interchange (EDI)

General Terms:
Algorithms, Performance, Security

Keywords:
broadcast authentication, one-time signature, signature based on a one-way function without trapdoor, source authentication for multicast