Approximately optimal trees for group key management with batch updates |
| |
Authors: | Minming Li Ze Feng Nan Zang Ronald L Graham Frances F Yao |
| |
Affiliation: | 1. Department of Computer Science, City University of Hong Kong, Hong Kong;2. Department of Computer Science and Engineering, University of California at San Diego, United States |
| |
Abstract: | 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(n4) 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+? for any fixed ?>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. |
| |
Keywords: | Key management Key trees Batch update Approximation algorithms Optimality |
本文献已被 ScienceDirect 等数据库收录! |
|