Optimal key tree structure for deleting two or more leaves

Weiwei Wu; Minming Li; Enhong Chen

doi:10.1007/978-3-540-92182-0_10

Optimal key tree structure for deleting two or more leaves

Weiwei Wu, Minming Li, Enhong Chen

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

4 Citations (Scopus)

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)²∈-∈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.

Original language	English
Title of host publication	Algorithms and Computation
Subtitle of host publication	19th International Symposium, ISAAC 2008, Proceedings
Publisher	Springer Verlag
Pages	77-88
Volume	5369 LNCS
ISBN (Print)	3540921818, 9783540921813
DOIs	https://doi.org/10.1007/978-3-540-92182-0_10
Publication status	Published - 2008
Event	19th International Symposium on Algorithms and Computation, ISAAC 2008 - Gold Coast, QLD, Australia Duration: 15 Dec 2008 → 17 Dec 2008

Publication series

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

Conference

Conference	19th International Symposium on Algorithms and Computation, ISAAC 2008
Place	Australia
City	Gold Coast, QLD
Period	15/12/08 → 17/12/08

Access Output

10.1007/978-3-540-92182-0_10

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Wu, W., Li, M., & Chen, E. (2008). Optimal key tree structure for deleting two or more leaves. In Algorithms and Computation: 19th International Symposium, ISAAC 2008, Proceedings (Vol. 5369 LNCS, pp. 77-88). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5369 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-92182-0_10

Wu, Weiwei ; Li, Minming ; Chen, Enhong. / Optimal key tree structure for deleting two or more leaves. Algorithms and Computation: 19th International Symposium, ISAAC 2008, Proceedings. Vol. 5369 LNCS Springer Verlag, 2008. pp. 77-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{134e6d6640b1496fb7a968990fe98d7c,

title = "Optimal key tree structure for deleting two or more leaves",

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. {\textcopyright} 2008 Springer Berlin Heidelberg.",

author = "Weiwei Wu and Minming Li and Enhong Chen",

year = "2008",

doi = "10.1007/978-3-540-92182-0_10",

language = "English",

isbn = "3540921818",

volume = "5369 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "77--88",

booktitle = "Algorithms and Computation",

address = "Germany",

note = "19th International Symposium on Algorithms and Computation, ISAAC 2008 ; Conference date: 15-12-2008 Through 17-12-2008",

}

Wu, W, Li, M & Chen, E 2008, Optimal key tree structure for deleting two or more leaves. in Algorithms and Computation: 19th International Symposium, ISAAC 2008, Proceedings. vol. 5369 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5369 LNCS, Springer Verlag, pp. 77-88, 19th International Symposium on Algorithms and Computation, ISAAC 2008, Gold Coast, QLD, Australia, 15/12/08. https://doi.org/10.1007/978-3-540-92182-0_10

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 32 - Refereed conference paper (with host publication) › peer-review

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 -

Wu W, Li M, Chen E. Optimal key tree structure for deleting two or more leaves. In 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)). doi: 10.1007/978-3-540-92182-0_10

Optimal key tree structure for deleting two or more leaves

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this