Trees for group key management with batch update

Due to the tremendous increase in bandwidth of the network, the group-oriented broadcast services are becoming increasingly popular. These group-oriented broadcast services, such as teleconferencing and pay-per-view TV, have a large number of subscribers and a central group controller (GC), which is in charge of all the security related administrative tasks. All the members in the group share a key called the Traffic Encryption Key (TEK), and the messages broadcast by the group members are encrypted by the TEK. For security reasons, if there is a group membership change, the TEK has to be updated. So, the GC needs to send some rekeying messages. To minimize the number of rekeying messages, an efficient and popular method is to arrange the members in a tree structure and assign the auxiliary keys, called the Key Encryption Key (KEK), to the members belonging to a same subtree. The problem of finding an optimal tree structure to minimize the rekeying messages to be sent is called the Group Key Management (GKM) problem. The tree structures are called Group Key Management trees. The group Key Management problem has been a popular research topic for several years. Many models have been proposed. In this dissertation, we mainly focus on a batch rekeying model. In this model, the number of group members n is fixed and each member has probability p (p=1-q) of being replaced by a new member during a batch period. In this dissertation, we focus on the problem of constructing "good" trees and analyzing the properties of GKM optimal trees for fixed q and n. Two efficient approximation algorithms are proposed to construct such trees: one is for the limiting case when the number of group members becomes unbounded and the other is for the limiting case as q is close to 1. We also relax the GKM problem to a more general mathematical problem, called the Jumping Sequence Problem. We give detailed analysis of the properties of the jumping sequences. Based on those properties, we also provide a lower bound for optimal GKM tree