Optimal key tree structure for deleting two or more leaves

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

2 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationAlgorithms and Computation
Subtitle of host publication19th International Symposium, ISAAC 2008, Proceedings
PublisherSpringer Verlag
Pages77-88
Volume5369 LNCS
ISBN (Print)3540921818, 9783540921813
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5369 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title19th International Symposium on Algorithms and Computation, ISAAC 2008
PlaceAustralia
CityGold Coast, QLD
Period15 - 17 December 2008

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 5∈ ∈d∈ ∈7 where the number of leaves in the subtrees differs by at most one and each subtree is a 2-3 tree. © 2008 Springer Berlin Heidelberg.

Citation Format(s)

Optimal key tree structure for deleting two or more leaves. / Wu, Weiwei; Li, Minming; Chen, Enhong.

Algorithms and Computation: 19th International Symposium, ISAAC 2008, Proceedings. Vol. 5369 LNCS Springer Verlag, 2008. p. 77-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5369 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)