Approximately Optimal Trees for Group Key Management With Batch Updates

The authors investigate the group key management problem for broad-casting applications. Previous work showed that, in handling key up-dates, 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(n4) time when p ?¨ 0. In this paper, they investigate more efficient algorithms for the case p ?¨ 0, i.e., when membership changes are sparse.