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 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 provede 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]