10-05-2012, 11:03 AM
multicast groups is dynamic and requires
mar.docx (Size: 58.11 KB / Downloads: 28)
1 INTRODUCTION
APPLICATIONS such as conferencing, distributed interactive
simulations, networked gaming, and news dissemination
are group-oriented. In these applications, it is
necessary to secure the group communication as the data
are sensitive or it requires the users to pay for it. In the
algorithms for secure group communication (e.g., [1], [2],
[3], [4], [5], [6], [7], [8], [9], [10], [11]), a group key is shared
by all the users. The group key is used to encrypt data
transmitted to the group. The group membership is
dynamic. When group membership changes, to protect
the confidentiality of the current users, a new group key
needs to be shared by the users.
The dynamics of the group membership can be handled
under two settings.
In the first setting, a central group controller manages the group membership and the users do not have the necessity to communicate among themselves.
Scenarios like pay TV, news dissemination, stock information, etc., are in this category.
In these scenarios, typically, the group size is large and geographically disparate.
In the second setting, the group members collaborate to agree upon a common group key [8], [9], [10], [11]. Applications like conferencing and distributed interactive simulation fall under this category. The group sizes in such applications
are typically small and justifies the usage of the relatively
high end computation required by the group key agreement
techniques [8], [9], [10], [11], [12]. In this work, we consider
the first setting where a large group of users is managed by
a group controller and consider the cost of membership
handling in such applications.
When a user is admitted to the group, the group
controller changes the group key and securely unicasts it
to the joining user. To send the new group key to the
current users, the group controller encrypts it with the old
group key and multicasts it to them. Thus, the cost of
rekeying for the group controller, due to a joining user is
small. However, when a user is revoked, i.e., the user leaves
or is forcefully removed from the group, the group
controller needs to securely unicast the new group key to
each of the remaining users. Toward this, the group
controller encrypts the new group key with the personal
keys of each of the remaining users and unicasts each
message to the respective user. The cost of this process is
OðNÞ symmetric key encryptions and OðNÞ messages.
Thus, for a large group, revoking users from the secure
group is an expensive operation.
Many solutions have been proposed (e.g., [2], [3], [4], [5],
[7]) for efficiently handling a single membership change,
i.e., a single join or revocation of a user. In these solutions,
for a group of N users, the group controller distributes the
new group key in OðlogNÞ encrypted messages. We note
that in these solutions, the rekeying cost, i.e., number of
encryptions performed and messages transmitted by the
group controller, for a joining user is increased from two to
OðlogNÞ. However, techniques suggested in [7], [13] reduce
the join cost to nearly constant and as such have been used
by other approaches [4], [14], [15], [16]. On the other hand,
the cost for revoking a user is reduced from OðNÞ to
OðlogNÞ encrypted messages. However, to handle multiple
membership changes, the group controller repeats the
process of revocation for each revoked user. Optimizations
58 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 8, NO. 1, JANUARY-FEBRUARY 2011
. B. Bruhadeshwar is with the International Institute of Information
Technology, Room 309, Block B (CSTAR), Gachibowli, Hyderabad,
500032, Andhra Pradesh, India. E-mail: bezawada[at]iiit.ac.in.
. S.S. Kulkarni is with the Department of Computer Science and
Engineering, Michigan State University, 3115 Engineering Building East
Lansing, MI 48824. E-mail: sandeep[at]cse.msu.edu.
Manuscript received 1 Aug. 2007; revised 20 Feb. 2008; accepted 19 Mar.
such as batch [17] or periodic rekeying [18] reduce this cost
to some extent. However, even in these solutions, the cost of
revocation is high. Moreover, as the group controller needs
to interrupt the group communication during the rekeying,
the resulting delay can be unreasonable for many applications.
Thus, efficient distribution of the new group key for
multiple membership changes is a critical problem in secure
group communication.
One approach to revoke multiple users is to associate a
key with every nonempty subset of users in the group. Thus,
if one or more users are revoked, the group controller uses
the key associated with the subset of the remaining users to
encrypt the new group key and transmits the new group key
to them. The advantage of this approach is that the
communication overhead is only one message for revoking
any number of users. However, the number of keys stored
by the group controller and the users is exponential in the
size of the group. In this paper, we describe a family of key
management algorithms that reduce the cost due to multiple
user revocation while keeping the storage cost manageable.
The goal of the paper is to evaluate trade-off between
storage and revocation cost. Storage is computed in terms of
keys that each user (respectively, group controller) maintains.
And revocation cost is computed in terms of the
encryptions performed, and the number of messages
transmitted, by the group controller. Similar to the algorithms
in [2], [3], [4], [5], [7], [13], [17], [18], [19], [20], [21], we
assume that the communication from the group controller
is broadcast in nature. Using our algorithms, the group
controller can efficiently distribute the group key. The main
contributions of our paper are as follows:
. We describe our family of key management algorithms
for efficiently distributing the new group key
when multiple users are revoked from the group. In
our algorithms, the storage at the group controller is
linear and the storage at the users is logarithmic in the
size of the group. Also, we show that some popular
algorithms (e.g., [3], [4]) are members of this family.
. We describe techniques to reduce the number of
keys stored by the users and the group controller.
Using one-way hash functions, we describe two key
assignment techniques. We show that our key
assignment techniques can be used to add users to
the group and to provide preferential treatment to
long standing users in the group. We argue the
applicability of our algorithms to scenarios where
users have varying requirements or capabilities.
. We also describe a hybrid key management algorithm
by combining our algorithm with an existing
solution. We show that such a combination is useful
when users have varying computational requirements.
Moreover, if these requirements vary over
time, our algorithms can be adapted to them
accordingly. The hybrid key management algorithm
proves that our algorithm can be easily composed
with any existing key management algorithm in an
incremental basis.