Optimizing deletion cost for secure multicast key management

Multicast and broadcast are efficient ways to deliver messages to a group of recipients in a network. Due to the growing security concerns in various applications, messages are often encrypted with a secret group key. The key tree model which has been widely adopted maintains a set of keys in a tree structure so that in case of group member change, the group key can be updated in a secure and efficient way. In this paper, we focus on the updating cost incurred by member deletions. To implement a sequence of member deletions in any key tree, a certain number of encrypted messages need to be broadcast to accomplish the updates. Our goal is to identify the best key tree which can minimize the worst-case deletion cost (i.e., the amortized cost over n member deletions). We prove that there is an optimal tree in which each internal node has at most five children and each internal node with at least one non-leaf child has exactly three children. Based on these characterizations, we present a dynamic programming algorithm that computes an optimal key tree in O(n2) time.