An Information Theoretic Approach for Design and Analysis of Rooted-Tree Based Multicast Key Management Schemes

Recent literature presents several rooted tree based member deletion/revocation schemes [20, 21, 22, 24, 4, 5] trying to simultaneously minimize the key storage while providing ecient member dele-tion/revocation. Many of these approaches have dierent solutions and provide dierent values for the number of keys to be stored and distributed. In this paper, we show that many of these papers can be systematically studied using basic concepts from information theory. In particular, we show that the entropy of member revocation event, plays a major role in dening the key allocation requirements. We then relate the entropy of member revocation event to provide bounds on the key length. We also show that the optimal Human coding strategy used in [22, 24] leads to security weakness. A method for generating Key management schemes with varying degrees of member collusion is also presented in this paper