Approximately Optimal Trees for Group Key Management with Batch Updates

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

5 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation
EditorsJin-Yi Cai, S. Barry Cooper, Hong Zhu
PublisherSpringer
Pages284-295
ISBN (Electronic)9783540725046
ISBN (Print)3540725032, 9783540725039
Publication statusPublished - May 2007

Publication series

NameLecture Notes in Computer Science
Volume4484
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title4th International Conference on Theory and Applications of Models of Computation (TAMC 2007)
PlaceChina
CityShanghai
Period22 - 25 May 2007

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 (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 (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.

Citation Format(s)

Approximately Optimal Trees for Group Key Management with Batch Updates. / Li, Minming; Feng, Ze; Graham, Ronald L.; Yao, Frances F.

Theory and Applications of Models of Computation. ed. / Jin-Yi Cai; S. Barry Cooper; Hong Zhu. Springer, 2007. p. 284-295 (Lecture Notes in Computer Science; Vol. 4484).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)