Lower Bounds for Multicast Message Authentication

  • Dan Boneh
  • Glenn Durfee
  • Matt Franklin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)


Message integrity from one sender to one receiver is typically achieved by having the two parties share a secret key to compute a Message Authentication Code (MAC). We consider the “multicast MAC”, which is a natural generalization to multiple receivers. We prove that one cannot build a short and efficient collusion resistant multicast MAC without a new advance in digital signature design.


  1. 1.
    R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, “Multicast Security: A taxonomy and some efficient constructions”, in IEEE INFOCOM'99, vol. 2, pp. 708–716, 1999.Google Scholar
  2. 2.
    A. De Santis and M. Yung, “On the design of provably-secure cryptographic hash functions”, in Proc. of Eurocrypt '90, LNCS 473, pp. 412–431, 1990.Google Scholar
  3. 3.
    Y. Desmedt, Y. Frankel, and M. Yung, “Multi-receiver/Multi-sender network security: efficient authenticated multicast/feedback”, in IEEE INFOCOM '92, pp. 2045–2054, 1992.Google Scholar
  4. 4.
    F. Fujii, W. Kachen, and K. Kurosawa, “Combinatorial bounds and design of broadcast authentication”, in IEICE Trans., vol. E79-A, no. 4, pp. 502–506, 1996.Google Scholar
  5. 5.
    R. Gennaro and P. Rohatgi, “How to sign digital streams”, in Proc. of Crypto '97, 1997.Google Scholar
  6. 6.
    S. Goldwasser, S. Micali, and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks”, SIAM Journal of Computing, vol. 17, pp. 281–308, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    P. Golle, N. Modadugo, “Streamed authentication in the presence of random packet loss”, in Proc..of 8th Annual Internet Society Symposium on Network and Distributed System Security (NDSS '01), San Diego, 2001.Google Scholar
  8. 8.
    K. Kurosawa, S. Obana, “Characterization of (k, n) multi-receiver authentication”, in Information Security and Privacy, ACISP '97, LNCS 1270, pp. 205–215, 1997.CrossRefGoogle Scholar
  9. 9.
    M. Naor and M. Yung, “Universal one-way hash functions and their cryptographic applications”, in Proc. of 21st Annual ACM Symposium on Theory of Computing, pp. 33–43, 1989.Google Scholar
  10. 10.
    A. Perrig, R. Canetti, D. Tygar, D. Song, “Efficient Authentication and Signature of Multicast Streams over Lossy Channels”, in Proc. of 2000 IEEE Symposium on Security and Privacy, Oakland, 2000.Google Scholar
  11. 11.
    A. Perrig, R. Canetti, D. Song, D. Tygar, “Efficient and Secure Source Authentication for Multicast”, in Proc. of 8th Annual Internet Society Symposium on Network and Distributed System Security (NDSS '01), San Diego, 2001.Google Scholar
  12. 12.
    P. Rohatgi, “A compact and fast hybrid signature scheme for multicast packet authentication”, in Proc. of 6th ACM conference on Computer and Communication Security, 1999.Google Scholar
  13. 13.
    J. Rompel, “One-way functions are necessary and sufficient for secure signatures”, in Proc. of 22nd Annual ACM Symposium on Theory of Computing, pp. 387–394, 1990.Google Scholar
  14. 14.
    R. Safavi-Naini, H. Wang, “Multireceiver authentication codes: models, bounds, constructions and extensions”, Information and Computation, vol. 151, no. 1/2, pp. 148–172, 1999.zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    R. Safavi-Naini, H. Wang, “New results on multireceiver authentication codes”, in Proc. of Eurocrypt '98, LNCS 1403, pp. 527–541, 1998.Google Scholar
  16. 16.
    G. Simmons, “A cartesian product construction for unconditionally secure authentication codes that permit arbitration”, J. Cryptology, vol. 2, no. 2, pp. 77–104, 1990.zbMATHCrossRefMathSciNetGoogle Scholar
  17. 17.
    C. K. Wong, S. S. Lam, “Digital signatures for flows and multicasts”, IEEE ICNP '98. Also, University of Texas Austin, Computer Science Technical report TR 98-15.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Dan Boneh
    • 1
    • 2
  • Glenn Durfee
    • 1
    • 2
  • Matt Franklin
    • 1
    • 2
  1. 1.Department of Computer ScienceUniversity of CaliforniaDavis
  2. 2.Computer Science DepartmentStanford UniversityStanfordUSA

Personalised recommendations