An Information Theoretic Analysis of Rooted Tree Based Multicast Key Distribution Schemes

An Information Theoretic Analysis of Rooted Tree Based Multicast Key Distribution Schemes

Title : An Information Theoretic Analysis of Rooted Tree Based Multicast Key Distribution Schemes
Authors :
Poovendran, Radha.
Baras, John, S.
Conference : Crypto’99: 19th Annual IACR Crypto Conference pp.624-638
Date: August 15 - August 19, 1999

Several variations of rooted tree based solutions have been recently proposed for member revocation in multicast communications [18 ,19,20,21] .In this paper we show that by assigning Probabilities for member revocations,the optimality correctness and the system requirements of some these schemes [18,19,20,21 ] can be systematically studied using information theoretic concepts. Specifically, we show that the optimal average number of keys per member in a rooted tree is related to the entropy of the member revocation event. Using our derivation we show that (a) the key assignments in [18, 21, 20, 19] corresponds to the maximum entropy solution, (b) and direct application of source coding will lead to member collusion (we present recently proposed solutions [21, 20] as examples of this) and a general criteria that admits member collusion. We also show the relationship between entropy of member revocation event and key length.

Download Full Paper