2008 | OriginalPaper | Buchkapitel
Optimal Key Tree Structure for Deleting Two or More Leaves
verfasst von : Weiwei Wu, Minming Li, Enhong Chen
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 5 ≤
d
≤ 7 where the number of leaves in the subtrees differs by at most one and each subtree is a 2-3 tree.