TY - GEN
T1 - Optimal key tree structure for deleting two or more leaves
AU - Wu, Weiwei
AU - Li, Minming
AU - Chen, Enhong
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=58549120227&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-58549120227&origin=recordpage
U2 - 10.1007/978-3-540-92182-0_10
DO - 10.1007/978-3-540-92182-0_10
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 3540921818
SN - 9783540921813
VL - 5369 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 77
EP - 88
BT - Algorithms and Computation
PB - Springer Verlag
T2 - 19th International Symposium on Algorithms and Computation, ISAAC 2008
Y2 - 15 December 2008 through 17 December 2008
ER -