Optimal Communication Complexity of Generic Multicast Key Distribution

Date Added: Jan 2011
Format: PDF

The authors 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. The lower bound shows that for any group of size n, on the average, one needs to transmit at least log2 (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.