Optimal tree structures for group key management with batch updates

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

15 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)532-547
Journal / PublicationSIAM Journal on Discrete Mathematics
Issue number2
Publication statusPublished - 2007


We investigate the key management problem for broadcasting applications. Previous work showed that batch rekeying can be more cost-effective than individual rekeying. Under the assumption that every user has probability p of being replaced by a new user during a batch rekeying period, we study the structure of the optimal key trees. Constant bounds on both the branching degree and the subtree size at any internal node are established for the optimal tree. These limits are then utilized to give an O(n) dynamic programming algorithm for constructing the optimal tree for n users and any fixed value of p. In particular, we show that when p > 1 - 3-1/3 ≈ 0.307, the optimal tree is an n-star, and when p ≤ 1 - 3-1/3, each nonroot internal node has a branching degree of at most 4. We also study the case when p tends to 0 and show that the optimal tree resembles a balanced ternary tree to varying degrees depending on certain number-theoretical properties of n. © 2007 Society for Industrial and Applied Mathematics.

Research Area(s)

  • Batch updates, Group keys, Key trees, Optimality