A lower bound for multicast key distribution
Jack Scott Snoeyink, Subhash Suri, George Varghese · 2002
With the rapidly growing importance of multicast in the Internet there have been a proposal, the RFC 2627, for scalable key distribution such that when the nth user joins or leaves a group, broadcasting /spl Theta/(logn) encrypted messages is sufficient to redistribute the keys. We show that this bound is also necessary for a general class of key distribution schemes and under different assumptions on user capabilities. While key distribution schemes can trade addition cost for deletion cost, for any scheme there is a sequence of 2n insertion and deletions whose total cost is /spl Omega/(nlogn). Thus, any key distribution scheme has a worst-case cost of /spl Omega/(logn) either for adding or for deleting a user.