Optimizing deletion cost for secure multicast key management

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

11 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)52-61
Journal / PublicationTheoretical Computer Science
Volume401
Issue number1-3
Publication statusPublished - 23 Jul 2008

Abstract

Multicast and broadcast are efficient ways to deliver messages to a group of recipients in a network. Due to the growing security concerns in various applications, messages are often encrypted with a secret group key. The key tree model which has been widely adopted maintains a set of keys in a tree structure so that in case of group member change, the group key can be updated in a secure and efficient way. In this paper, we focus on the updating cost incurred by member deletions. To implement a sequence of member deletions in any key tree, a certain number of encrypted messages need to be broadcast to accomplish the updates. Our goal is to identify the best key tree which can minimize the worst-case deletion cost (i.e., the amortized cost over n member deletions). We prove that there is an optimal tree in which each internal node has at most five children and each internal node with at least one non-leaf child has exactly three children. Based on these characterizations, we present a dynamic programming algorithm that computes an optimal key tree in O (n2) time. © 2008 Elsevier B.V. All rights reserved.

Research Area(s)

  • Dynamic, Key tree, Optimization, Security

Citation Format(s)

Optimizing deletion cost for secure multicast key management. / Chen, Zhi-Zhong; Feng, Ze; Li, Minming; Yao, Frances.

In: Theoretical Computer Science, Vol. 401, No. 1-3, 23.07.2008, p. 52-61.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal