Title: Optimal Key Tree Structure for Deleting Two or More Leaves 

Speaker: Li Minming
CityU HK

Date: Friday  May 15, 2009
Time 11:00-11:50
Venue: Room 3464, HKUST

Abstract: 
We study the optimal tree structure for the key management problem.
In the key tree, when two or more leaves are deleted or replaced,
the updating cost is defined to be the number of encryptions needed
to securely update the remaining keys. Our objective is to find the
optimal tree structure where the worst case updating cost is
minimum. We first prove the degree upper bound (k+1)2-1 when k
leaves are deleted from the tree. Then we focus on the 2-deletion
problem and prove that the optimal tree is a balanced tree with
certain root degree 4< d < 8 where the number of leaves in the
subtrees differs by at most one and each subtree is a 2-3 tree.