Lower Bounds for Multicast Message Authentication

Authors: D. Boneh, G. Durfee, and M. Franklin

Message integrity between two parties is typically achieved by having them share a secret key to compute a Message Authentication Code (MAC). Unfortunately, this does not generalize well to the multicast settings. Consequently, integrity for multicast messages often relies on digital signatures: The sender signs the outgoing broadcast and the various receivers verify the signature. It is natural ask whether digital signatures are necessary for multicast message integrity, or whether a more lightweight mechanism can suffice. We prove that one cannot build a short collusion resistant multicast MAC without relying on digital signatures. This is in contrast to standard two party MACs that do not require signatures.

In proceedings of Eurocrypt '2001, Lecture Notes in Computer Science, Vol. 2045, Springer-Verlag, pp. 437--452, 2001

Full paper: PostScript