Approximately optimal trees for group key management with batch updates

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

14 Scopus Citations
View graph of relations

Author(s)

  • Minming Li
  • Ze Feng
  • Nan Zang
  • Ronald L. Graham
  • Frances F. Yao

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1013-1021
Journal / PublicationTheoretical Computer Science
Volume410
Issue number11
Online published6 Nov 2008
Publication statusPublished - 6 Mar 2009

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.

Research Area(s)

  • Approximation algorithms, Batch update, Key management, Key trees, Optimality

Citation Format(s)

Approximately optimal trees for group key management with batch updates. / Li, Minming; Feng, Ze; Zang, Nan; Graham, Ronald L.; Yao, Frances F.

In: Theoretical Computer Science, Vol. 410, No. 11, 06.03.2009, p. 1013-1021.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal