**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.

[DOI:10.1007/b97182]**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.