Probabilistic optimization techniques for multicast key management
The logical key hierarchy (LKH) scheme and its derivatives are among the most efficient protocols for multicast key management. Traditionally, the key distribution tree in an LKH-based protocol is organized as a balanced binary tree, which gives a uniform O(log n) complexity for compromise recovery in an n-member group. In this paper, we study improving the performance of LKH-based key distribution protocols by organizing the LKH tree with respect to the members' rekeying probabilities instead of keeping a uniform balanced tree. We propose two algorithms, which combine ideas from data compression with the special requirements of multicast key management. Simulation results show that these algorithms can reduce the cost of multicast key management significantly, depending on the amount of variation in the rekey characteristics of the group members.