Internet Engineering Task Force Radhakrishna Sampigethaya
INTERNET-DRAFT Mingyan Li
Radha Poovendran
Dept. of Electrical Engineering
University of Washington, Seattle
C. Berenstein
University of Maryland, College Park
April, 2002
Centralized Key Management and Distribution for Dynamic
Multicast Groups: Scalability Issues
<draft-radha-msec-ckmd-01.txt>
Status of this Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet
Engineering Task Force (IETF), its areas, and its working
groups. Note that other groups may also distribute working
documents as Internet Drafts.
Internet-Drafts are draft documents valid for a maximum of
six months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-
Drafts as reference material or to cite them other than as
"work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed
at http://www.ietf.org/shadow.html.
This document expires on October, 2002
Sampigethaya, Li, Poovendran, Berenstein [Page 1]
INTERNET-DRAFT April 2002
Abstract:
=========
We present our work on efficient scalable solutions to the hierarchical
key management and distribution problem for secure multicast sessions.
We take two rooted-tree based schemes that solve hierarchical key
management and distribution problem and then present ways of making
these schemes more efficient by reducing the tree center key storage
with an upper bound on key update communication. The objective of
improving efficiency is posed as a constrained optimization problem,
which we further reduce to a fixed-point equation and find solutions.
We also provide a tree design algorithm, which allows the designer to
specify an upper key update communication bound and construct an
efficient tree with minimal center storage while maintaining pre-
existing logarithmic scalability in time and space requirements. The
choice of update communication bound as a design factor is the recent
development of multicast communication applications, which have energy
or bandwidth as constraints, and these in turn being directly related
to communication bounds.
Sampigethaya, Li, Poovendran, Berenstein [Page 2]
INTERNET-DRAFT April 2002
Table of Contents:
==================
1. Introduction ------------------------------------------------ 4
1.1 Multicast vs. Unicast ------------------------------------ 4
1.2 Multicast security --------------------------------------- 5
1.3 Key management and distribution -------------------------- 5
1.4 The efficiency factors ----------------------------------- 6
2. Key Management and Distribution schemes --------------------- 7
2.1 Previous related work ------------------------------------ 7
2.2 Hierarchical Tree based schemes -------------------------- 8
2.2.1 Logical Key Hierarchy (LKH) tree scheme ------------- 9
2.2.2 One-way Function Tree (OFT) scheme ------------------ 10
2.2.3 One-way Function Chain (OFC) scheme ----------------- 13
2.2.4 Comparison between LKH, OFT, OFC -------------------- 14
2.3 Minimal Storage Scheme ----------------------------------- 15
2.4 The Hybrid Approach -------------------------------------- 16
2.4.1 Communication-Storage tradeoff ---------------------- 16
2.4.2 The Approach ---------------------------------------- 16
3. Hybrid LKH or Enhanced LKH ---------------------------------- 17
4. Hybrid OFT or Enhanced OFT ---------------------------------- 19
5. Minimization of GC storage with Communication bound --------- 20
5.1 Minimization of GC storage ------------------------------- 20
5.2 Update Communication budget or bound --------------------- 20
5.3 Constrained Optimization --------------------------------- 21
5.4 Application to the hybrid schemes ------------------------ 21
5.4.1 Hybrid LKH ------------------------------------------ 21
5.4.2 Hybrid OFT ------------------------------------------ 24
6. Hybrid Tree Construction design algorithm ------------------- 25
7. Performance Analysis ---------------------------------------- 26
7.1 Comparison of results ------------------------------------ 26
7.2 Design Examples ------------------------------------------ 27
7.2.1 Design example of a Hybrid LKH ---------------------- 27
7.2.2 Design example of a Hybrid OFT ---------------------- 28
8. Conclusion and open problems -------------------------------- 28
9. References -------------------------------------------------- 29
10. Author's Addresses ----------------------------------------- 31
11. Acknowledgements ------------------------------------------- 31
Sampigethaya, Li, Poovendran, Berenstein [Page 3]
INTERNET-DRAFT April 2002
1. Introduction:
================
With the advent of various group oriented communication applications
such as video conferencing, tele-conferencing and Internet gaming,
there is a need to focus on multicast mode of communication.
1.1 Multicast vs. Unicast:
--------------------------
Multicasting has taken a clear precedence over unicasting in group
communication applications such as multimedia communication in which a
sender has to send identical data simultaneously to group members. An
example would be a pay-per-view session where the members have paid the
cable operator for the movie and need to receive the transmission.
Multicast communication or point to multipoint communication in
particular has inherent virtues that efficiently utilize the network
resources and also considerably reduce computational overhead of the
sender. At times multicast communication involves transmission of just
one message, which is then transmitted, to the entire group by the
multicasting infrastructure. Fig. 1 illustrates a typical multicast
session taking place with a single sender and N users. The multicasting
infrastructure in this case consists of the communication links and the
multicast router. Unicast communication, on the other hand, involves
higher sender overhead and poor network resource utilization for most
group-oriented communications. This is illustrated in Fig. 2. where the
sender needs to transmit the same message N times, once to each user,
resulting in sender overhead and inefficient network bandwidth
utilization.
-->
---------O User 1
/ -->
/----------O User 2
message / -->
--> /------------O User 3
O------------------O .
Sender Multicast \ :
Router \ :
\ :
\ .
----------O User N
-->
Fig. 1: Multicast Communication Mode where the group sender
------ has to send a single message into the infrastructure to
transmit the message to all other group users.
Sampigethaya, Li, Poovendran, Berenstein [Page 4]
INTERNET-DRAFT April 2002
message
-->
--------------O User 1
/ message
/ -->
Sender O-----------------O User 2
\ .
\ :
\ :
\ message :
\ --> .
-------------O User N
Fig. 2: Unicast Communication Mode where the group sender
------ has to send the same message N times.
1.2 Multicast Security:
-----------------------
Despite its advantages, for wide scale deployment of multicast
communication, especially on the Internet, one has to make the
communication secure. By secure multicast communication we mean two
things: one, is making sure that the information from the sender is
securely transmitted over the network and two, is making sure that the
sender transmitted information is not accessed by entities outside the
multicast group. A possible approach towards secure multicast is the
use of encryption using cryptographic keys. Encrypting data would make
it secure over the network and using keys would provide data access
control only to group members who have the keys. Access control can be
essentially mapped down to the management and distribution of the
cryptographic keys. The goal is to provide key management and
distribution schemes that are efficient and will maintain the virtuous
properties of multicast communication while securing it at the same
time. A balance has to be maintained that would retain the performance
of multicast while also making it secure. This tradeoff is of course
dependent on the application and what level of security or performance
it requires.
1.3 Key Management and Distribution:
------------------------------------
In a multicast group, there will be a trusted entity termed as the
Group Center (GC). GC will be responsible for generating and updating
the cryptographic keys. A sender in the group will use a key that is
stored by the GC and is known to the entire group. This key is called
Session Encryption Key (SEK) or Traffic Encryption Key (TEK). All the
data the sender transmits is encrypted using the SEK and so the
intended group members will then access the data by performing
decryption using the SEK. However, every time a member leaves the
group or joins the group then we face a security threat. When a member
leaves the group we need to provide forward security in that we need to
change the SEK so that the departed member can't access future group
communications. When a member joins the group we need to provide
Sampigethaya, Li, Poovendran, Berenstein [Page 5]
INTERNET-DRAFT April 2002
backward security in that we need to change the SEK so that the new
member can't access any of the past group communications. Hence
updating the SEK is very essential when there is any change in group
membership. It is also a healthy practice to do a periodic update of
the SEK even when there is no membership change.
In order to distribute the updated SEK to the group members the GC
would now need another set of keys. This set of keys is termed as Key
Encryption Keys (KEK). Every group member will have a KEK that it
shares only with the GC so that the GC could transmit the new SEK
securely to it.
1.4 The Efficiency Factors:
---------------------------
We consider two factors to assess the efficiency of a key management
and distribution scheme. Note that in the context of our discussion,
efficiency also means scalability. The efficiency factors are:
1. Key Storage
2. Key Update communication
Key storage is the number of keys that need to be stored by the GC (GC
storage) and any group member (member/user storage).
Key Update communication is the total communication cost involved in
updating the existing keys for every group membership change, and can
be given by the expression,
i=|UM|
__
\
/__ S_i
i=1
where S_i is the size of the ith update message. |UM| is the total
number of update messages for every group membership change.
Note:
i=ul
___
\
/___ (F(i))
i=ll
is the notation for the summation of an expression 'F(i)' with i
ranging from ll to ul.
Key Update communication can also alternatively be looked at as the GC
computational overhead because, essentially, for each communication
with a user, the GC has to perform encryption with that user's KEK.
The update process is also referred to as rekeying. Group membership
changes maybe in the form of member addition, member deletion or member
Sampigethaya, Li, Poovendran, Berenstein [Page 6]
INTERNET-DRAFT April 2002
revocation. Member addition will require a relatively simpler rekeying
process as the new member would not be aware of the old SEK upon
joining the group and hence that SEK can be used to encrypt the updated
SEK to the pre-existing group members. However, member deletion
(revocation) would require a relatively more complex rekeying process
as the member being deleted or revoked would know the old SEK hence
proving it useless for any kind of current as well as future encryption
use. Hence the focus of rekeying schemes is on the member deletion
event. A special member deletion event that may take place is one where
more than one member is being deleted simultaneously in which case
there is concern of a possible security breach from member collusion
(Note: Member collusion is a process where two or more group members
get together or collude to break the security of that group).
2. Key Management and Distribution Schemes:
===========================================
A trivial and naive key management and distribution scheme for a
multicast group of size N would have a flat structure with GC key
storage as N+1 which is essentially the single SEK and the N KEK's. The
user key storage would be 2, which is essentially the user's KEK and
the SEK. The key update communication for this scheme would however be
as high as the group size N because every time a user of the group is
deleted, the GC needs to communicate the new SEK to each of the
remaining users of the group. For large N, the GC storage would also be
high for this scheme. However the update communication is more
expensive in terms of scalability as it occurs everytime there is a
change in group membership.
As we can see, the above scheme would definitely not be scalable in
terms of GC storage and update communication for large multicast groups
and would reach worst case performance for a large group with high
member dynamics (frequent group membership changes). However, it is a
scheme that is secure against any kind of user collusion.
2.1 Previous related work:
--------------------------
Research efforts have produced efficient scalable group key management
and distribution schemes. However, there is always a tradeoff between
the key update communication and the GC key storage. This has been
discussed in detail by Canetti et al. in [Can1]. Different approaches
have been taken to yield scalable solutions to the key management and
distribution problem.
Harney and Muckenhirn [Harn1] proposed a solution called GKMP (Group
Key Management Protocol) that has a group SEK and a group KEK for the
GC and a single KEK for the user. Hence the scheme has a GC storage of
N+2, user storage of 3, and update communication of N-1, making it not
scalable especially in terms of update communication. Several
hierarchical tree-based schemes have been proposed [Can1, Can2, McGr1,
Wall1, Wong1] and these schemes have a better scalability, due to the
Sampigethaya, Li, Poovendran, Berenstein [Page 7]
INTERNET-DRAFT April 2002
structure of the tree. Schemes proposed in [Can2, McGr1], however, also
use cryptographic key computational relations between the tree levels
to improve scalability. We discuss in detail in the following sections
some of these tree-based schemes which have improved scalability. Also
there have been various schemes that, apart from scalability, are
designed for security in terms of user collusion. One of the earliest
work on multicast security key management was conducted by Fiat and
Naor [Fiat1]. Their key distribution scheme is resilient to collusion
by up to a specified number, k, of users. The scheme, however,
requires a user storage of O(k log(k)log(n)) keys and an update
communication of O(k^2 {log(k)}^2 log(n)) messages, where n is the
total number of users in the group. Many other schemes for improved
secure multicast key management have been proposed since then.
However, our focus in this document is on the scalability of key
management and distribution schemes for secure multicast rather than
the security of the scheme. We also assume a reliable multicast
protocol for our communication leading to the additional assumption
that there are no losses of rekey messages. There are previous works
such as [Perr1] [Yang1] which propose a reliable key distribution
protocol. In [Perr1], the authors present a reliable protocol called
ELK. This scheme provides reliability for key update messages without
relying on reliable multicast protocols, using hint messages. The
scheme in [Yang1] provides reliability for rekey messages, using
proactive forward error correction (FEC). Yet another interesting
related work in key management and distribution scalability is that of
R.Poovendran et al. [RP4] in which tree-based schemes are analyzed by
using information theoretic approach, and the minimum number of keys to
be updated under a member deletion event is proved to be related to the
entropy of member deletion statistics.
2.2 Hierarchical Tree based schemes:
------------------------------------
The most popular and accepted solution to scalable key management and
distribution that exists today is the hierarchical tree based scheme
because of its inherent logarithmic scalability. We consider the
following three different hierarchical tree schemes:
Logical Key Hierarchy (LKH) tree of Wallner et al. [Wall1] and Wong et
al. [Wong1]
One-way Function Tree (OFT) of McGrew and Sherman [McGr1]
One-way Function Chain (OFC) of Canetti et al. [Can2]
Sampigethaya, Li, Poovendran, Berenstein [Page 8]
INTERNET-DRAFT April 2002
2.2.1 Logical Key Hierarchy (LKH) tree scheme:
----------------------------------------------
K_0 <------Root key
O
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
K_11 / \ K_12 <------- Node key
O O
/ \ / \
/ \ / \
/ \ / \
K_21/ \ K_22 K_23/ \K_24 <----- Node key
O O O O
/ \ / \ / \ / \
/ \ / \ / \ / \
O O O O O O O O
K_31 K_32 K_33 K_34 K_35 K_36 K_37 K_38 <---- Leaf Keys
M1 M2 M3 M4 M5 M6 M7 M8 <---- Members
Fig. 3: A binary LKH tree for a group of 8 members.
------
Fig. 3 above shows a typical LKH tree proposed by Wallner et al.
[Wall1]. The degree of the tree shown is binary i.e. 2, but it can be
in general of degree a.
Key storage:
In the tree, each group member is assigned to a unique leaf node, thus
fixing the number of leaves to be the group size N. Since the number of
leaves determines the height of a tree, the height of the tree is also
fixed and so is the total number of tree nodes in this model. Every
node of the logical tree is assigned a KEK. The set of keys assigned to
the nodes along the path from a leaf node to the root are assigned to
the member associated with that particular leaf node. For example,
member M1 is assigned KEK's {K_0, K_11, K_21, K_31}. The member storage
is thus 4 in this case and in general it will be the height of the
tree, given as (1+log_a(N)) for a tree of given degree a.
{Note: log_a() means log base a}. The GC has to store the keys
corresponding to the nodes of the entire tree, which is
(aN - 1 )/(a - 1). Hence, the key storage requirement of the GC and a
group member will scale as O(N) and O(log N) respectively.
Sampigethaya, Li, Poovendran, Berenstein [Page 9]
INTERNET-DRAFT April 2002
Key Update Communication:
Since a member shares the root key and all the intermediate KEK's with
other users, all the keys possessed by a member except the one at the
leaf node have to be updated when the member is deleted. For example,
when M1 leaves, {K_0, K_11, K_21} plus the SEK need to be updated.
K_31, which is the KEK of the leaf node, can be deleted without any
update. The number of key update messages is then given as
(a log_a(N)). Hence, the key update communication of the GC in this
scheme will scale as O(log N).
Therefore we see that the GC storage is a bottleneck for the
scalability of a LKH tree scheme. An approach that would maintain the
logarithmic scalability of update communication and member storage
while further reducing the GC storage is therefore desired. This is
further discussed in Section 3.
2.2.2 One-way Function Tree (OFT) scheme:
-----------------------------------------
K_0=f(g(K_11),g(K_12)) <------Root key
*
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
f(g(K_21),g(K_22))=K_11 K_12=f(g(K_23),g(K_24)) <- Node key
* + |
/ \ / \ |
/ \ / \ V
/ \ / \
f(g(K_31),g(K_32))=K_21 K_22 K_23 K_24=f(g(K_37),g(K_38))
* + O O
/ \ / \ / \ / \
/ \ / \ / \ / \
@ + O O O O O O
K_31 K_32 K_33 K_34 K_35 K_36 K_37 K_38 <---- Leaf Keys
M1 M2 M3 M4 M5 M6 M7 M8 <---- Members
@ - unblinded keys assigned to member M1
+ - blinded keys assigned to member M1
* - unblinded keys known to member M1
O - keys unknown to member M1
Fig. 4: A binary OFT for a group of 7 members with a new member M8
------ requesting to join the group
Sampigethaya, Li, Poovendran, Berenstein [Page 10]
INTERNET-DRAFT April 2002
One-way function tree (OFT) was proposed by McGrew and Sherman in
[McGr1] and by Balenson, McGrew, and Sherman in [McGr2] to further
reduce the update communication of the LKH by a factor of two for
binary trees, and a factor of a/(a-1) for a-ary trees. Unlike LKH where
the keys on the tree are assumed to be independent, the keys on OFT are
related by one-way function with a computational scheme that allows the
derivation of a high level node key from keys of all its children
nodes, hence reducing the rekey messages per update.
Key Storage:
Every member of the group is uniquely assigned to a leaf node on the
tree, thus fixing the number of leaves to be the group size N. For
every node x in the tree, there are two associated keys: an unblinded
node key K_x, and a blinded node key K_x'. {Note: Only unblinded keys
are shown in Fig. 4}. The blinded node key is the output of one-way
function g with the unblinded node key as the input, i.e., K_x'=g(K_x).
It is computationally infeasible for those knowing K_x' to derive K_x
[McGr1].
Unblinded keys are used to encrypt and decrypt rekey messages. Blinded
keys allow computing unblinded keys of higher levels from lower levels,
thus reducing the number of new keys the GC has to encrypt and
multicast during key updates. This will in turn reduce the update
communication.
The OFT works as follows. The GC generates an unblinded key for each
leaf node, and the unblinded keys of interior tree nodes are computed
by applying a mixing function f to the blinded keys of all its
children. Explicitly, K_x is computed from the children of node x on
the OFT tree of degree a, as:
K_x = f(K_{child_1}', K_{child_2}', ..., K_{child_a}')
i.e. K_x = f(g(K_{child_1}), ..., g(K_{child_a}))
For example, given the keys K_31 and K_32', member M1 can compute K_21
as K_21 = f(g(K_31), K_32'). It is recommended that for efficiency
purpose, the mixing function f be chosen as XOR [McGr1]. If a member is
given the unblinded leaf key and the blinded keys of the siblings of
every node along the path from its leaf to the root, the member will be
able to compute all the unblinded keys along its path to the root to
decrypt necessary rekey messages. Since there are (a-1) siblings to a
node on each level and the height of a tree is log_a(N), a member needs
to store [1+(a-1)log_a(N)] keys. For example, in Fig. 4 member M1 has
to store the set of KEK's {K_31, K_32', K_22', K_12'}, i.e.
[1+(2-1)log_2(8)] = 4 keys. Since the GC needs to store only the N
unblinded keys of the leaf nodes, the storage is N, which is
independent of the degree of the tree. Hence we see that the
scalability of GC storage is O(N) and that of member storage is
O(log N).
Key Update Communication:
Member Addition in OFT:
Sampigethaya, Li, Poovendran, Berenstein [Page 11]
INTERNET-DRAFT April 2002
A new member has to be assigned to a unique leaf and a new unblinded
key needs to be associated with that node. The GC computes the keys
along the new member's key path and multicasts the new blinded keys to
the current siblings along the path. The new member is given necessary
keys using unicast. For example, in Fig. 4, if a new member M8 is added
into the group, the GC generates K_38 and recomputes interior keys. It
broadcasts E{K_38'}_{K_37}, E{K_24'}_{K_23}, E{K_12'}_{K_11} where the
notation E{m}_{K} denotes the encryption of message m with key K.
Member M7 decrypts K_38' to recompute K_24, K_12 and K_0; member M5 and
M6 decrypt K_24' to recompute K_12 and K_0. Therefore, the key update
communication for a member addition is the number of siblings on each
level times the height of the tree, given as (a-1)log_a(N).
Member Deletion in OFT:
When a member is deleted from the group, all the interior keys it once
shared with other members have to be updated. The GC computes new
blinded keys and then sends the keys to proper subgroups. The key
update communication for a member deletion is also given as
(a-1)log_a(N).
Hence in either case of membership dynamics, the scalability of key
update communication is logarithmic in group size N.
Sampigethaya, Li, Poovendran, Berenstein [Page 12]
INTERNET-DRAFT April 2002
2.2.3 One-way Function Chain (OFC) scheme:
------------------------------------------
K_0=f_l(f_r(f_r(r_21))) <------Root key
+
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
f_l(f_r(r_21))=K_11 K_12 <------- Node key
+ O |
/ \ / \ |
/ \ / \ |
f_l(r_21)=K_21 K_22 K_23 K_24 <----------|
+ O O O
/ \ / \ / \ / \
/ \ / \ / \ / \
O O O O O O O O
K_31 K_32 K_33 K_34 K_35 K_36 K_37 K_38 <---- Leaf Keys
M1 M2 M3 M4 M5 M6 M7 M8 <---- Members
|
|
V
Member being revoked
O - unblinded keys
+ - updated unblinded keys
Fig. 5: A binary OFC scheme for 8 group members with
------ member M1 being revoked from the group
This scheme was proposed by Canetti et al. in [Can2]. It is an improved
version of OFT and the authors have shown their scheme to be more
secure compared to the OFT scheme.
The tree structure of OFC is similar to that of OFT. However, the
functions, f and g, are not the same for OFC scheme. The very choice of
the function f used makes the OFC scheme relatively more secure
[Blum1]. The security of OFT is based on non-standard cryptographic
assumptions and has not been rigorously proven.
In OFC, f is a pseudo-random generating function with the length of its
output being double of its input [Blum1]. If x is the input to f, then
its output f(x) consists of f_l(x) and f_r(x), the left and right
halves respectively, and f(x)=f_l(x) || f_r(x) (where || represents
concatenation). f_l(x) and f_r(x) are computationally independent and
Sampigethaya, Li, Poovendran, Berenstein [Page 13]
INTERNET-DRAFT April 2002
the solidarity of the function f defines the security of OFC scheme.
Key Storage and Update Communication:
All the leaf nodes of the tree are assigned unblinded keys by the GC as
in OFT. Unblinded keys are used to encrypt and decrypt rekey messages.
In Fig. 5 we have a binary OFC scheme for eight members and it depicts
a user revocation event. Member M1 is being deleted/revocated from the
group. Upon its deletion, a random number r_21 is generated, encrypted
with the key K_32 and then transmitted by the GC. The member M2 would
then recompute the parent node key that it had shared with M1. More
specifically, the following takes place:
f(r_21) is first computed. f_l(r_21) is assigned be the new K_21. Then
f(f_r(r_21)) is computed. f_l(f_r(r_21)) is assigned to be the new
K_11. Finally, f(f_r(f_r(r_21))) is computed, and then
f_l(f_r(f_r(r_21))) is assigned to be the new root KEK. The GC will
also perform the following encryptions (and transmissions):
Encryption of r_21 wih K_32, encryption of f_r(r_21) with K_22, and
encryption of f_r(f_r(r_21)) with K_12. Hence the update communication
for this scenario is 3. In general, we can compute the update
communication for an a-ary tree to be (a-1) log_a(N). This is because
there will be (a-1) siblings which would need the updated key at each
of the log_a(N) tree levels.
The GC storage would be O(N) as the number of leaf nodes will be fixed
by the group size N. The user storage, though numerically slightly less
than OFT, will still be O(log N).
2.2.4 Comparison between LKH, OFT, OFC:
---------------------------------------
Comparison between LKH and OFT:
Both the LKH, OFT and OFC have a tree structure, and the height of the
tree determines the user st has been rigorously
proved because of the solidarity of pseudo-random function used in
OFC. In [Can 2] the authors have claimed the security of OFC to be
better than that of LKH. More specifically, if assuming that a third
party, which is capable of decrypting encryptions in a certain subpace
Sampigethaya, Li, Poovendran, Berenstein [Page 14]
INTERNET-DRAFT April 2002
(referred to as 'weak subspace'), takes control of the GC, then the
third party could generate keys on the LKH tree such that they appear
to be random, but the encryptions that use these keys would always be
in the weak subpace. Hence a third party could hack into the
communications of a multicast group which uses the LKH scheme.
However, in the OFC scheme, the root key as well all other keys on the
tree except the leaf keys are derived by the GC using a pseudo-random
function. The use of a secure pseudo-random function (used in [Can 2])
makes it difficult to define a weak subspace, because the application
of the random function makes the possible number of key values
(i.e. the subspace) to increase dramatically and hence requiring a very
large amount time and computation power for decrypting encryptions in
that space. This claim by [Can 2] is based on the security from the
group center point of view.
2.3 Minimal Storage Scheme:
---------------------------
K_0 <------------- SEK
r <------------- random seed
/\
/| \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
/ | \
o ........ o ......... o
K_1=f_r(1) K_i=f_r(i) K_N=f_r(N)) <----- KEK's
M_1 M_i M_N <----- Members
Fig. 6: Minimal Storage Scheme for a group of size N.
------
Fig. 6 shows a simple key management and distribution scheme that has
minimal storage for GC and the group members. This scheme was presented
by Canetti et al in [Can1]. The GC stores the SEK and a random seed r,
which is the index of a pseudo-random function f_r [Gold]. The GC
generates an unique KEK for each member by using the member index as
input to the function f_r(). In notation, for a member i, its KEK is
K_i=f_r(i). Hence we see that the GC needs to store only the random
seed r and the SEK, while each member needs to store the SEK and its
Sampigethaya, Li, Poovendran, Berenstein [Page 15]
INTERNET-DRAFT April 2002
unique KEK, thus leading to a minimal storage of 2 keys for both the
GC and each group member. However, the key update communication of this
scheme scales linearly in group size N, as the GC needs to update each
member individually with the new SEK.
2.4 The Hybrid Approach:
------------------------
2.4.1 Communication-Storage tradeoff:
-------------------------------------
We have so far seen that there are two schemes, one of which is the
hierarchical tree based scheme having logarithmic key update
communication and user storage but linear GC key storage and the second
one being the minimal storage scheme having minimal GC and user storage
but linear key update communication. We need to tradeoff communication-
storage in order to approach a more efficient scheme. Also tradeoff is
essential in order to cater to the various possible multicast
communication scenarios. This tradeoff is discussed in more detail by
Canetti et al in [Can1]. Intuitively, one would think of combining the
two schemes in order to achieve a tradeoff between communication and
storage.
2.4.2 The approach:
-------------------
A group of size N is divided into clusters, each of size M. Thus we
will have N/M clusters. Each cluster will be assigned a leaf node of a
hierarchical tree, the height of which would now be dependent not only
on the group size but also on the cluster size M. Hence the
hierarchical tree scheme is employed between the clusters. However,
within each cluster, minimal storage scheme is employed. This would
cause the GC storage of the hybrid or combined scheme to be reduced as
the number of leaf nodes would now be N/M (sub-linear) instead of N
(linear), with each leaf node having 2 keys assigned to it, one being
the unique KEK and the other being a unique random seed which would be
common to the members of a cluster. Also, the update communication of
the hybrid scheme would be restricted to a logarithmic scale because of
the hierarchical tree scheme.
Hence the two schemes are combined in order to tradeoff communication
and storage parameters and to finally approach a more efficient scheme.
We need to note that, by combining the hierarchical tree scheme with
minimal storage scheme, we do not modify the security properties of the
hierarchical tree scheme and hence we preserve the security of the
original tree scheme. In the following two sections, we discuss two
hybrid approaches.
Sampigethaya, Li, Poovendran, Berenstein [Page 16]
INTERNET-DRAFT April 2002
3. Hybrid LKH or Enhanced LKH:
==============================
-- K_0 <------Root key
| O
| / \
| / \
| / \
| / \
| / \
Logical / \
Tree / \
| / \
| K_11 / \ K_12 <---- Node keys
| O O
| / \ / \
| / \ / \
| / \ / \
| K_21/ \ K_22 K_23/ \K_24 <-- Leaf keys
-- O O O O
| /|\ /|\ /|\ /|\
Clusters / | \ / | \ / | \ / | \
| O O O O O O O O O O O O
-- K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 M12 <- Members
|_______| |
| | |
| V |
| Cluster Size M=3 |
| |
|_____________________________________________|
|
V
Group Size N=12 Height of tree: log_2(N/M)
Fig. 7: A binary hybrid-LKH tree scheme with group size 12 and
------ cluster size 3.
This scheme was proposed by Canetti et al. in [Can1]. In LKH tree
scheme the GC needs to store all the keys on the tree. For a tree of
given degree, the GC storage is therefore dependent on the height of
the tree which is turn is dependent on number of leaves in the tree. If
the number of leaves is set as a variable, then it is possible to
control the total number of keys stored by the GC. One approach [Can1]
is to cluster the members and assign multiple members to a leaf, and
then by controlling the number of members assigned to a leaf node, we
can vary the total number of nodes in the tree and thus the number of
keys stored in the GC. This approach is the hybrid-LKH or enhanced LKH
scheme.
Fig. 7 shows a typical hybrid LKH tree scheme of degree 2 for a group
size N=24 and a cluster size M=3.
Sampigethaya, Li, Poovendran, Berenstein [Page 17]
INTERNET-DRAFT April 2002
The structure consists of two parts, the logical tree, and the
clusters. The LKH tree is used as inter-cluster key management scheme
to limit key update communication, and the minimal storage used as the
intra-cluster scheme to reduce GC storage requirement.
Key Storage and Update Communication:
For a hybrid-LKH tree scheme of degree a, a user needs to store
(1+log_a(N/M)) KEK's required by the logical key tree scheme plus one
KEK required by the minimal storage scheme within the cluster. The
number of keys stored by the GC is computed as the keys on the tree
plus seeds for N/M clusters, which is
i=log_a(N/M)
___
\
/___ (a^i) + N/M = {1 + (a/(a-1))}N/M - {1/(a-1)}
i=0
= (2a-1)N/(a-1)M
got by ignoring the last term 1/(a-1) which is at most 1 since a>=2.
Note: X^i is the notation for X raised to the power of i.
When a member is deleted, the number of key update messages is
(a log_a(N/M) within the tree plus (M-1) within the cluster, leading to
a total of (M-1 + (a log_a(N/M))).
Sampigethaya, Li, Poovendran, Berenstein [Page 18]
INTERNET-DRAFT April 2002
4. Hybrid OFT or Enhanced OFT:
==============================
-- K_0=f(g(K11),g(K12)) <------Root key
| O
| / \
| / \
| / \
| / \ Node keys
| / \ |
Logical / \ |
Tree / \ V
| / \
f(g(K21),g(K22))=K_11 K_12=f(g(K23),g(K24))
| O O
| / \ / \
| / \ / \
| / \ / \
| K_21/ \ K_22 K_23/ \K_24 <-- Leaf keys
-- O O O O
| /|\ /|\ /|\ /|\
Clusters / | \ / | \ / | \ / | \
| / | \ / | \ / | \ / | \
| O O O O O O O O O O O O
-- K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12
M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 M12 <- Members
| |_________| |
| | |
| V |
| Cluster Size M=3 |
| |
|__________________________________________|
|
V
Group Size N=12 Height of tree: log_2(N/M)
Fig. 8: A binary hybrid-OFT tree scheme with group size 12 and
------ cluster size 3.
This scheme was presented by R. Poovendran et. al. in [RP2].
In the OFT scheme the GC storage is equal to the number of leaves in
the tree. Once again by setting the number of leaves as a variable, we
can control the GC storage. To achieve this goal is to multiple members
are assigned to a leaf node. Then by controlling the number of members
assigned to a leaf node, we can vary the number of leaves and thus the
GC storage. The main idea, like for hybrid-LKH, is to divide the group
of size N into clusters of size M with every cluster assigned to a
unique leaf node. Then there are N/M clusters (also leaves) and we need
to build a tree of depth log_a(N/M). Fig. 8 illustrates a binary hybrid
Sampigethaya, Li, Poovendran, Berenstein [Page 19]
INTERNET-DRAFT April 2002
OFT with cluster size M=3 and group size N=12. The structure consists
of two parts, the OFT, and the clusters. The OFT scheme is used as
inter-cluster key management scheme to limit key update communication,
and the minimal storage is used as the intra-cluster scheme to reduce
GC storage requirement. The combined scheme is called hybrid OFT or
enhanced OFT.
Key Storage and Update Communication:
In the hybrid tree presented in Fig. 8, a user needs to store
(1+(a-1)log_a(N/M)) KEK's required by the OFT scheme, plus one KEK
required by the minimal storage scheme within the cluster. The number
of keys stored by the GC, computed as the number of leaves of the
hybrid OFT plus seeds for N/M clusters, is 2N/M. When a member is
deleted, the total number of key update messages is (a-1)log_a(N/M)
within the tree plus (M-1) within the cluster, leading to a total of
(M -1 + (a-1)log_a(N/M)) update messages.
5. Minimization of GC storage with Communication bound:
=======================================================
We have seen that tradeoff between GC storage and update communication
is required to achieve improved key management and distribution
schemes. There are multicast applications in which the communication
cost is bounded. Communication costs can be in terms of the energy or
bandwidth that is expended in the process of communication. In such
scenarios, it is useful to formulate the tradeoff in terms of an
optimization problem. The problem of optimizing (minimizing) the GC
storage, given a pre-specified update communication bound is addressed
by R. Poovendran et al. in [RP1, RP2].
5.1 Minimization of GC storage:
-------------------------------
Minimization of the GC storage will cause the memory requirements to
meet stringent limits that exist for certain multicast applications.
Let S denote the GC storage of a key management and distribution
scheme.
5.2 Update Communication budget or bound:
-----------------------------------------
The communication costs related to key updates need to be low in order
to maintain the advantage of multicast communication in the application
using it. Energy and bandwidth are the normal costs associated with
communication. Let C denote the key update communication cost
associated with a key management and distribution scheme. Let B denote
the pre-specified communication upper bound or budget.
Sampigethaya, Li, Poovendran, Berenstein [Page 20]
INTERNET-DRAFT April 2002
5.3 Constrained Optimization:
-----------------------------
The minimization of GC storage with a pre-specified update
communication bound can be posed as a constrained optimization problem.
The function to be optimized (minimized) is the GC storage, S, and the
constraint is the communication cost C which is bounded by a pre-
specified upper bound.
In notation,
min(S) given the constraint C<=B. We will now discuss this optimization
for the hybrid schemes.
5.4 Application to the hybrid schemes:
--------------------------------------
We have so far seen that the hybrid schemes provide logarithmic user
storage and update communication cost while providing sub-linear GC
storage. Hence while minimizing GC storage we need to maintain the
logarithmic scalability of the scheme. However, the update
communication cost is flexible till the upper bound is reached.
5.4.1 Hybrid LKH:
-----------------
Canetti et al [Can1] mentioned that by making the cluster size M=log N,
the GC storage for the hybrid LKH can be reduced to O(N/log N).
R. Poovendran et al. [RP1] presented minimization of GC storage with a
given pre-specified key update communication bound for hybrid LKH
scheme. A detailed mathematical analysis of an efficient hybrid LKH
tree follows:
For hybrid LKH we have:
C = M-1 + (a log_a(N/M)) --------------------------- (1)
S = (1+ a/(a-1))N/M --------------------------- (2)
In order to maintain the efficiency of the scheme it is required to
keep the update communication as log_a(N) except some scale factor B,
which is the pre-specified bound on update communication. This can be
expressed as:
C <= B log_a(N)
i.e. M -1 + (a log_a(N/M)) <= B log_a N,
The optimization problem:
-------------------------
The storage and the update communication are both functions of the
cluster size M. Hence the optimization problem is posed as:
min((1+a/(a-1))N/M ) w.r.t M
subject to the communication constraint,
M -1 + (a log_a(N/M)) <= Blog_a N
Sampigethaya, Li, Poovendran, Berenstein [Page 21]
INTERNET-DRAFT April 2002
B is the pre-specified bound on update communication and since we need
to also maintain the pre-existing logarithmic update communication of
the scheme we combine the two objectives into the bound shown above.
The selection of M should be such that the update communication scales
at least as O(log_a(N)) while the key storage of the GC is better than
O(N). We now solve for the optimization problem by working towards
finding the optimal M.
The solution:
-------------
The following theorem presents the solution to the constraint
optimization problem.
Theorem: Optimal cluster size M that minimizes the storage function
S = (2a-1)N/(a-1)M while satisfying the update communication budget
C = M-1 + (a log_a(N/M)) <= (B log_a(N)) is obtained by the largest
root of the equation M - lambda(ln(M)) = u, where
lambda = a/ln(a) and u = 1 + (B-a)log_a(N).
Note: ln() is the notation for log_e()
Proof: A comprehensive proof follows. Since the storage is a
monotonically decreasing function of M, the largest value of M
satisfying the update communication constraint will be the solution of
this constraint optimization.
Solving,
M-1 + (a log_a(N/M)) = B log_a(N)
M-1 + (a log_a(N)) - (a log_a(M)) = B log_a(N)
M-1 + (a ln(N)/ln(a)) - (a ln(M)/ln(a)) = B log_a(N)
Hence, the optimal value of the cluster size is computed by the
equation:
M + lambda(ln(N)) - lambda(ln(M)) - 1 = B log_a(N) -------------(3)
The update communication, given in (1) and in the left-hand side of
(3), is a convex function of M and its minimum value can be got by:
finding the derivative of (1) w.r.t M and equating it to 0, finding the
value of M at which the minima occurs, substituting this value of M
back in the equation (1). That is:
Taking derivative of (1) w.r.t M and equating it to 0,
1 + 0 - lambda(1/M) - 0 = 0
The value of M at which the minima occurs is therefore,
M = lambda
Substituting this value of M back in (1),
C_min={lambda(1+ln(N/lambda)) - 1} at M=lambda.
Sampigethaya, Li, Poovendran, Berenstein [Page 22]
INTERNET-DRAFT April 2002
From equation (3), we see that at M=lambda where the minimum update
communication occurs,
lambda(1+ln(N/lambda)) - 1 = B log_a(N)
i.e. B = {lambda(1+ln(N/lambda))-1}/log_a(N) ------------------ (4)
This is a lower bound for the pre-specified update communication
budget. Hence,
B >= {lambda(1+ln(N/lambda))-1}/log_a(N)
should be satisfied in order to solve (3), which gives us the optimal
value of cluster size M.
For large values of N, we can algebraically prove that the asymptotic
lower bound of B approaches (a-1).
Eq (3) can be re-written as,
M - lambda(ln(M))= B log_a(N) - (a log_a(N)) + 1
i.e. M - lambda(ln(M)) = (B - a)log_a(N) + 1
i.e. M - lambda(ln(M)) = u ---------------------------------(5)
where u = (B - a)log_a(N) + 1
Computing the cluster Size M:
-----------------------------
The fixed-point equation (5) is a contraction mapping with the largest
root as the fixed-point solution, if we start the iteration with an
initial value M_0 > lambda. Notice that this equation is nonlinear and
thus need series approximation. We therefore derive the solution using
the first order Taylor series approximation with Newton's method [RP3].
By setting M_0 = u, the first-order approximation is
M_1 = u + lambda(ln(u)).
Letting N->infty, yields
M_infty = u + lambda(ln(u)) ~= u = 1 + (B - a)log_a(N) -----(6)
This is the asymptotic solution to the optimization problem.
Note: 'infty' is the notation for infinity and '~=' is the notation for
approximation.
An alternative solution would be to use the series approximation:
i=infty
___
M = u | | {1+(lambda/u)^i (ln(u))} ---------------------------(6a)
i=1
Sampigethaya, Li, Poovendran, Berenstein [Page 23]
INTERNET-DRAFT April 2002
Note: i=ul
___
| | (F(i)) is the notation for series product of an expression
i=ll F(i) with i ranging from ll to ul.
The asymptotic value of M, M_infty can be approximated by the value
given by (6). However, eq (6a) provides the option of improving the
approximation or accuracy of computation of M to any desirable level.
For large values of N, the largest root of the equation (3) converges
to M_infty and hence grows as O(log_a(N)).
Computing Minimal Storage S:
----------------------------
We next compute the corresponding value of the GC storage denoted by
S_infty.
S_infty = (2a-1)N /((a-1)(B - a)log_a(N)) --------------- (7)
Hence, the constraint optimization leads to the optimal growth of the
GC storage as O(N/log_a(N)) which is far better than O(N) growth, when
the update communication is constrained to grow as O(log_a(N)).
5.4.2 Hybrid OFT:
-----------------
The application of constrained optimization to hybrid OFT is presented
in [RP2].
For hybrid LKH we have:
C = M-1 + (a-1)log_a(N/M) --------------------------- (8)
S = 2N/M --------------------------- (9)
Note that GC storage for this scheme is independent of the degree of
the tree.
The optimization problem:
-------------------------
The storage and the update communication are both functions of the
cluster size M. Hence the optimization problem is posed as:
min((2N/M ) w.r.t M
subject to the communication constraint,
M -1 + (a-1)log_a(N/M) <= Blog_a N
where B is the pre-specified bound on update communication.
Sampigethaya, Li, Poovendran, Berenstein [Page 24]
INTERNET-DRAFT April 2002
The solution:
-------------
The solution for this optimization problem follows a similar path as
the previous solution for optimization problem of hybrid LKH. In the
end we get the same asymptotic solution for cluster size M as:
M_infty = u + lambda(ln(u)) ~= u = 1 + (B - a + 1)log_a(N) ------(10)
And the alternative series approximation solution as:
i=infty
___
M = u | | {1+(lambda/u)^i (ln(u))} ---------------------------(10a)
i=1
where in both (10) and (10a), lambda = (a-1)/ln(a) and
u = 1 + (B-a+1)log_a(N).
Note that for hybrid LKH, these two variables were different.
Computing Minimal Storage S:
----------------------------
We compute the corresponding asymptotic value of the GC storage denoted
by S_infty.
S_infty = 2N /((B - a + 1)log_a(N)) --------------- (11)
Hence, in the case of hybrid OFT also, the constraint optimization
leads to the optimal growth of the GC storage as O(N/log_a(N)) which is
far better than O(N) growth, when the update communication is
constrained to grow as O(log_a(N)).
6. Hybrid Tree Construction design algorithm:
=============================================
An explicit design procedure based on the design solution just
discussed is given below. This design procedure can be applied to
construct an efficient hybrid LKH tree or hybrid OFT with the GC
storage minimized under pre-specified update communication constraint.
Hybrid Tree Design Steps:
-------------------------
A. Initial design data: group size N, communication scale factor or
budget B, and degree of tree a (choose a=2 if not specified).
B. Check the condition for B given by:
B >= {lambda(1+ln(N/lambda))-1}/log_a(N)
where for hybrid LKH, lambda = a/ln(a) and
for hybrid OFT, lambda = (a-1)/ln(a)
Sampigethaya, Li, Poovendran, Berenstein [Page 25]
INTERNET-DRAFT April 2002
If condition is satisfied, go to step C. Otherwise the design, under
the given specifications, is not feasible.
C. Compute the first order approximation of the optimal cluster size M
using:
M_infty = 1 + (B - a)log_a(N) for hybrid LKH and
M_infty = 1 + (B - a + 1)log_a(N) for hybrid OFT.
or alternatively its nth order approximation by using:
i=inf
___
M = u | | {1+(lambda/u)^i (ln(u))} where u=1 + (B - a)log_a(N)
i=1 for hybrid LKH
u=1 + (B - a + 1)log_a(N)
for hybrid OFT
D. Construct a hybrid LKH/OFT of degree a and cluster size M
7. Performance Analysis:
========================
We have done a few non-exhaustive performance simulations for the LKH
and OFT schemes. The results are given below.
7.1 Comparison of schemes:
--------------------------
===================================================================
| Degree a, | No. of keys | No. of keys | Storage | Comm. |
| Group Size N | in GC by | in GC by | Reduction | Increase |
| | logical tree | equation (7) | in % | in % |
===================================================================
| (2, 2^10) | 2047 | 444 | 78.3 | 1.7 |
|-------------------------------------------------------------------
| (3, 2^10) | 1535 | 370 | 75.9 | 3.4 |
|-------------------------------------------------------------------
| (4, 2^10) | 1365 | 345 | 74.7 | 1.7 |
|-------------------------------------------------------------------
| (2, 2^20) | 2097151 | 226920 | 89.2 | 13.2 |
|-------------------------------------------------------------------
| (4, 2^20) | 1398101 | 176490 | 87.4 | 13.2 |
===================================================================
Table 1: Comparison of results for improved LKH (hybrid LKH) with LKH
---------------------------------------------------------------------
Sampigethaya, Li, Poovendran, Berenstein [Page 26]
INTERNET-DRAFT April 2002
===================================================================
| Degree a, | No. of keys | No. of keys | Storage | Comm. |
| Group Size N | in GC by | in GC by | Reduction | Increase |
| | logical tree | equation (14)| in % | in % |
===================================================================
| (2, 2^10) | 1024 | 205 | 80.0 | 31.4 |
|-------------------------------------------------------------------
| (3, 2^10) | 1024 | 325 | 68.3 | 19.1 |
|-------------------------------------------------------------------
| (4, 2^10) | 1024 | 410 | 60.0 | 11.6 |
|-------------------------------------------------------------------
| (2, 2^20) | 1048576 | 104858 | 90.0 | 45.4 |
|-------------------------------------------------------------------
| (4, 2^20) | 1048576 | 209715 | 80.0 | 23.9 |
===================================================================
Table 2: Comparison of results for improved OFT (hybrid OFT) with OFT
---------------------------------------------------------------------
From the above two tables, we see that, significant improvements can be
achieved in terms of GC storage by employing the hybrid approach. Using
optimal value for the cluster size M, and using the hybrid approaches,
a marked improvement in the GC storage is achieved under a given pre-
specified update communication bound. Column 4 in both the tables give
the improvement values for different group sizes and tree degrees.
7.2 Design examples:
--------------------
7.2.1 Design example of a Hybrid LKH:
-------------------------------------
For simulation, we first simplify the problem by setting
B=(1+lambda)ln(a) which leads to M_infty=ln(N) and
S_infty = (2a-1)N /{(a-1)ln(N)}. As a specific design example, we are
given the group size N=1000 and the degree of the tree a=3. The
communication budget factor B is set to be 3. The cluster size M is
computed as 8 by M_infty = 1 + (B - a + 1)log_a(N). A 3-ary tree with
cluster size 8 requires 313 keys to be stored in the GC, while the
update communication is less than 3log_3(N).
Sampigethaya, Li, Poovendran, Berenstein [Page 27]
INTERNET-DRAFT April 2002
7.2.1 Design example of a Hybrid OFT:
-------------------------------------
500-| +
| +
| +
400-| * +
| * +
| * +
S | * +
|% * +
| % * +
200-|---% * +
| | % * +
| | % * +
| | % * + +
| | % *
| | % * * *
0 | | % % %
----x-------------------------------------------
2 3 4 5 6 7 8 9 10
B
% - Plot for tree degree, a=2
* - Plot for tree degree, a=3
+ - Plot for tree degree, a=5
Fig. 10: GC Key Storage (S) vs Communication Scale Factor B
-------
We note that the optimal cluster size M, and hence the optimal storage
S are functions of the parameter B. From Fig. 10, it is seen that B can
be used as a design parameter to control the key storage of the GC.
Fig. 10, plots the key storage of the GC versus B for three different
tree degrees, a, based on equation (11).
For example, we choose a group size N=1000 and a tree degree a=2. It is
required that less than 200 keys be stored in the GC. From Fig. 10, we
can see that the communication scale factor B should be larger than
2.5. If B=3 is chosen, the optimal M can be computed as 25 using
equation (10). A binary hybrid tree with cluster size 25 requires only
120 keys to be stored in the GC according to (11) while the update
communication is 3log_2(N).
8. Conclusion and open problems:
================================
We have presented our work on an optimization-based approach to improve
the key storage performance of hierarchical tree based key management
and distribution schemes that are used for secure multicast sessions.
Sampigethaya, Li, Poovendran, Berenstein [Page 28]
INTERNET-DRAFT April 2002
We modified the structure of OFT, without changing the way the keys on
the tree are computed, and enhanced its scalability performance. We
then formulated the minimization of the center key storage of both the
LKH tree and OFT schemes, with pre-specified key update communication,
as constrained optimization problems. We further converted the
optimization problem for each scheme into a fixed-point equation, and
solved the equation for the optimal cluster size M by two methods. We
presented the first order approximation of the optimal cluster size M,
which is easy to compute in practice. We also presented a series
approximation, which allows increasing accuracy of computation to any
desired level. We showed that the center storage of the hybrid LKH and
the hybrid OFT could be reduced from linear to sub-linear. Based on our
modifications, we finally presented an explicit design algorithm for
the construction of a hybrid LKH and a hybrid OFT with a pre-defined
amount of key update communication.
The question whether there are tree schemes that would yield better
scalability than hierarchical tree schemes remains an open problem that
needs to be explored. Also, another open problem would be the question
whether there are schemes other than tree schemes, which would provide
better scalable solutions to the key management and distribution
schemes for secure multicast sessions.
9. References:
==============
[Blum1] M.Blum and S.Micali, "How to Generate Cryptographically
Strong Sequences of pseudo-Random Bits", SIAM J. on Comp., Vol. 13,
1984, 850-864.
[Can1] R.Canetti, T.Malkin, and K.Nissim, "Efficient Communication-
Storage Tradeoffs for Multicast Encryption", Eurocrypt'99, pp.456-470,
1999.
[Can2] R.Canetti, Juan Garey, Gene Itkis, Daniele Micciancio, Moni
Naor and B.Pinkas, "Multicast Security: A taxonomy and efficient
constructions", Infocomm99, 1999.
[Harn1] H.Harney, C.Muckenhirn, "Group Key Management Protocol
Architecture", RFC 2094, July 1997.
[McGr1] D.A.McGrew and A.T.Sherman, "Key Establishment in Large
Dynamic Groups: Using One-Way Function Trees", Technical Report 0755,
TIS Labs, 1998. A revised version is to appear in IEEE Trans. on
Software Engineering.
Sampigethaya, Li, Poovendran, Berenstein [Page 29]
INTERNET-DRAFT April 2002
[McGr2] D.Balenson, D.A.McGrew, A.T.Sherman, "Key Management for
Large Dynamic Groups: One-Way Function Trees and Amortized
Initialization," Internet Draft, 2000.
[Perr1] A.Perrig, D.Song, and J.D.Tygar, "ELK, a New Protocol for
Efficient Large-Group Key Distribution", IEEE Proceedings of Security
and Privacy, May 13-16, 2001, Oakland, California.
[RP1] M.Y.Li, R.Poovendran, C.Berenstein, "Optimization of Key
Storage for Secure Multicast", Proc. Conf on Information Science and
Systems, pp. 771-774, March 2001.
[RP2] M.Y.Li, R.Poovendran, D.A.McGrew, "Sender Key Storage
Reduction of Secure Multicast Key Management Schemes Using One-way
Function Tree", under submission.
[RP3] M.Y.Li, R.Poovendran, "Explicit design of Sub-linear trees
with pre-specified key update communication bound", The 51st IETF
Conference secure multicast group meeting, London, August 7th, 2001.
[RP4] R. Poovendran, J.S.Baras, "An Information Theoretic Approach
for Design and Analysis of Rooted Tree-Based Multicast Key Management
Schemes", IEEE Trans. on Information Theory, Nov 2001.
[Wall1] D.M.Wallner, E.J.Harder, and R.C.Agee, "Key Management for
Multicast: Issues and Architectures", RFC 2627, 1999.
[Wong1] C.K.Wong, M.Gouda, S.S.Lam, "Secure Group Communications
Using Key Graphs", IEEE/ACM Trans. on Networking, Vol.8, No.1, pp.16-31
2000.
[Yang1] Yang Richard Yang, X.Steve Li, X.Brian Zhang, Simon S.Lam
"Reliable Group Rekeying: A Performance Analysis", SIGCOMM '01, Aug
2001.
Sampigethaya, Li, Poovendran, Berenstein [Page 30]
INTERNET-DRAFT April 2002
10. Author's Addresses:
=======================
Radhakrishna Sampigethaya
Dept. of Electrical Engineering
University of Washington
Seattle, WA 98195-2500
USA
email: rkrishna@u.washington.edu
Tel: +1 206 616-1265
Mingyan Li
Dept. of Electrical Engineering
University of Washington
Seattle, WA 98195-2500
USA
email: myli@ee.washington.edu
Tel: +1 206 616-1265
Prof. Radha Poovendran
434 EE/CSE
Box 352500
University of Washington
Seattle, WA 98195-2500
USA
email: radha@ee.washington.edu
Tel: +1 206 221-6512
Prof. Carlos. A. Berenstein
Mathematics and the Institute for Systems Research
University of Maryland
College Park, MD 20742
USA
email: carlos@isr.umd.edu
Tel: +1 301 405-6845
11. Acknowledgments:
====================
We would like to thank Dr. Eric J. Harder at National Security Agency
(NSA) and David A. McGrew at Cisco Systems, for their useful comments.
Our work has been supported by the National Science Foundation under
NSF Faculty Career Development Award ANI 00-93187.
This document expires on October, 2002
Sampigethaya, Li, Poovendran, Berenstein [Page 31]