A novel high-order tree for secure multicast key management

Multicast is used to deliver packets to a group of users. To prevent users outside the group from eavesdropping, a group key is maintained to encrypt the group communication, and the group key is changed (rekeying) when a new member joins the group or an existing member leaves the group. Rekeying costs could be as high as n for a group with n members. The hierarchical key-tree approach is widely used to achieve logarithmic rekeying costs. However, the key tree has to be kept balanced in order to keep logarithmic rekeying costs. Goshi and Ladner propose the height-balanced 2-3 tree (a B-tree of order m=3) and found that it has the best performance among the balancing strategies tested. However, balancing a B-tree [J. Goshi et al., (2003)] after member joining involves splitting oversized tree nodes and results in (m+2)h worst-case rekeying cost, where h is the tree height. We propose an NSBHO (nonsplit balancing high-order) tree in which balancing tree after member joining does not involve node splitting, thus having 2h worst-case rekeying cost. An NSBHO tree is always balanced and its nodes may not satisfy the node properties of a standard B-tree. Our proposed NSBHO tree has the same worst-case rekeying cost incurred by a member removing as a B-tree [J. Goshi et al., (2003)] does. Our experiments show that the NSBHO tree has better average-case rekeying performance and far superior worst-case rekeying performance than a B-tree.