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(n 4) 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 further design a refined heuristic algorithm and show that it achieves an approximation ratio of 1 + ε as p →0.
This work was supported in part by the National Basic Research Program of China Grant 2007CB807900, 2007CB807901, the U.S. National Science Foundation Grant CCR-0310991, a grant from the Research Grants Council of Hong Kong under Project Number CityU 1165/04E and a grant from City University of Hong Kong (Project No. 7200072).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rafaeli, S., Hutchison, D.: A Survey of Key Management for Secure Group Communication. ACM Computing Surveys 35(3), 309–329 (2003)
Tamassia, R., Goodrich, M.T., Sun, J.Z.: Efficient Tree-Based Revocation in Groups of Low-State Devices. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 511–527. Springer, Heidelberg (2004)
Wong, C.K., Gouda, M.G., Lam, S.S.: Secure Group Communications Using Key Graphs. IEEE/ACM Transactions on Networking 8(1), 16–30 (2003)
Li, X.S., et al.: Batch Re-keying for Secure Group Communications. In: WWW10, Hong Kong, May 2-5 (2001)
Zhu, F., Chan, A., Noubir, G.: Optimal Tree Structure for Key Management of Simultaneous Join/Leave in Secure Multicast. In: Proceedings of MILCOM (2003)
Graham, R.L., Li, M., Yao, F.F.: Optimal Tree Structures for Group Key Management with Batch Updates. To appear in SIAM Journal on Discrete Mathematics.
Wallner, D., Harder, E., Agee, R.C.: Key Management for Multicast: Issues and Architectures. RFC 2627 (June 1999)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, M., Feng, Z., Graham, R.L., Yao, F.F. (2007). Approximately Optimal Trees for Group Key Management with Batch Updates. In: Cai, JY., Cooper, S.B., Zhu, H. (eds) Theory and Applications of Models of Computation. TAMC 2007. Lecture Notes in Computer Science, vol 4484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72504-6_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-72504-6_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72503-9
Online ISBN: 978-3-540-72504-6
eBook Packages: Computer ScienceComputer Science (R0)