Approximately optimal trees for group key management with batch updates

We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. One model for batch rekeying is to assume that every user has probability p of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when p is a constant and in O (n⁴) time when p → 0. In this paper, we investigate more efficient algorithms for the case p → 0, i.e., when membership changes are sparse. We design an O (n) heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We also design a refined heuristic algorithm and show that it achieves an approximation ratio of 1 + ε{lunate} for any fixed ε{lunate} > 0 and n, as p → 0. Finally, we give another approximation algorithm for any p ∈ (0, 0.693) which is shown to be quite good by our simulations.