Title:  Optimal Tree Structures for Group Key Management with Batch Updates 
Speaker:  Li Minming
City University of Hong Kong

Date: Friday, November 2, 2007
Time 11-12PM
Venue: Room  3464, HKUST

 
Abstract:
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 > 0.307, the optimal tree is an n-star, and when p < 0.307, 
each non-root internal node has branching degree 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.