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

R. Poovendran and J.S. Baras

IEEE Transactions on Information Theory, Vol. 47, No. 7, pp. 2824-2834, November 2001.

Abstract

Recent literature presents several seemingly different approaches to rooted-tree-based multicast key distribution schemes [6]–[8], [28], [29] that try to minimize the user key storage while providing efficient member deletion. In this paper, we show that the user key storage on rooted trees can be systematically studied using basic concepts from information theory. We show that the rooted-tree-based multicast key distribution problem can be posed as an optimization problem that is abstractly identical to the optimal codeword length selection problem in information theory. In particular, we show that the entropy of member deletion statistics quantifies the optimal value of the average number of keys to be assigned to a member. We relate the sustainable key length to statistics of member deletion event and the hardware bit generation rate. We then demonstrate the difference between the key distribution on rooted trees and the optimal codeword-length selection problem with an example of a key distribution scheme that attains optimality but fails to prevent user collusion [7], [8].