Optimal communication complexity of generic multicast key distribution

Authors: Daniele Micciancio and Saurabh Panjwani

Advances in Cryptology - Eurocrypt 2004. Interlaken, Switzerland, May 2-4, 2004. Lectture Notes in Computer Science 3027, Springer-Verlag, pp.153-170.

[BibTeX] [Postscript] [PDF]


Abstract: We prove a tight lower bound for generic protocols for secure multicast key distribution where the messages sent by the group manager are obtained by arbitrarily nested application of a symmetric encryption scheme, with random or pseudorandom keys. Our lower bound shows that for any group of size n, on the average, one needs to transmit at least log_2(n) messages in order to re-key the group. This lower bound matches (up to constant additive terms) the upper bound of Canetti, Garay, Itkis, Micciancio, Naor and Pinkas (Infocomm 1999), and is essentially optimal. Our result considerably strenghten previous lower bounds by Canetti, Malkin and Nissim (Eurocrypt 1999) and Snoeyunk, Suri and Varghese (Infocom 2001), which only applied to restricted classes of protocols, and in fact produced lower bounds that were higher than known upper bounds.