A survey of key management for secure group communication <s> Logical Key Hierarchy <s> Many emerging applications (e.g., teleconference, real-time information services, pay per view, distributed interactive simulation, and collaborative work) are based upon a group communications model, i.e., they require packet delivery from one or more authorized senders to a very large number of authorized receivers. As a result, securing group communications (i.e., providing confidentiality, integrity, and authenticity of messages delivered between group members) will become a critical networking issue.In this paper, we present a novel solution to the scalability problem of group/multicast key management. We formalize the notion of a secure group as a triple (U,K,R) where U denotes a set of users, K a set of keys held by the users, and R a user-key relation. We then introduce key graphs to specify secure groups. For a special class of key graphs, we present three strategies for securely distributing rekey messages after a join/leave, and specify protocols for joining and leaving a secure group. The rekeying strategies and join/leave protocols are implemented in a prototype group key server we have built. We present measurement results from experiments and discuss performance comparisons. We show that our group key management service, using any of the three rekeying strategies, is scalable to large groups with frequent joins and leaves. In particular, the average measured processing time per join/leave increases linearly with the logarithm of group size. <s> BIB001 </s> A survey of key management for secure group communication <s> Logical Key Hierarchy <s> This report contains a discussion of the difficult problem of key management for multicast communication sessions. It focuses on two main areas of concern with respect to key management, which are, initializing the multicast group with a common net key and rekeying the multicast group. A rekey may be necessary upon the compromise of a user or for other reasons (e.g., periodic rekey). In particular, this report identifies a technique which allows for secure compromise recovery, while also being robust against collusion of excluded users. This is one important feature of multicast key management which has not been addressed in detail by most other multicast key management proposals [1,2,4]. The benefits of this proposed technique are that it minimizes the number of transmissions required to rekey the multicast group and it imposes minimal storage requirements on the multicast group. <s> BIB002
Other contributions BIB001 and BIB002 ) propose the use of a Logical Key Hierarchy (LKH). In this approach, a KDC maintains a tree of keys. The nodes of the tree hold key encryption keys. The leaves of the tree correspond to group members and each leaf holds a KEK associated with that one member. Each member receives and maintains a copy of the KEK associated with its leaf and the KEKs corresponding to each node in the path from its parent leaf to the root. The key held by the root of the tree is the group key. For a balanced tree, each member stores at most (log 2 n) + 1 keys, where (log 2 n) is the height of the tree. For example, see Figure 1 , member u 1 knows k 1 , k 12 , k 14 and k. A joining member is associated with a leaf and the leaf is included in the tree. All KEKs in the nodes from the new leaf 's parent in the path to the root are compromised and should be changed (backward secrecy). A rekey message is generated containing each of the new KEKs encrypted with its respective node's children KEK. The size of the message produced will be at most 2 · (log 2 n) keys long. Figure 1 shows an example of the KEKs being affected. The new member u 3 receives a secret key k 3 and its leaf is attached to the node k 34 . The KEKs held by nodes k 34 , k 14 and k, which are the nodes in the path from k 3 to k, are compromised. New KEKs (k 34 , k 14 and k ) are generated as shown in Figure 2 . Finally, the KEKs are encrypted with each of its respective node's children KEK ({k 34 } k 3 ,k 4 ; {k 14 } k 12 ,k 34 ; and {k} k 14 ,k 58 (see Figure 2) . The size of a rekeying message for a balanced tree has at most 2 · (log 2 n) keys. Removing a member follows a similar process. When a member leaves (or is evicted from) the group, its parent node's KEK and all KEKs held by nodes in the path to the root are compromised and should be updated (forward secrecy). A rekey message is generated containing each of the new KEKs encrypted with its respective node's children KEK. The exception is the parent node of the leaving member's leaf. The KEK held by this node is encrypted only with the KEK held by the remaining member's leaf. As the key held by the leaving member was not used to encrypt any new KEK, and all its known KEKs were changed, it is no longer able to access the group messages. Figure 3 presents what happens when a member leaves. Member u 4 is leaving the group and it knows KEKs k 34 , k 14 and k. KEKs k 34 , k 14 and k are updated and encrypted with each of its respective children's KEKs. An exception is made for the k 34 . This KEK is encrypted only with k 3 , which is the key of the remaining member of n 34 . The algorithm proposed by  is different for joining operations. Instead of generating fresh keys and sending them to members already in the group, all keys affected by the membership change are passed through a oneway function. 4 Every member that already knew the old key can calculate the new one. Hence, the new keys do not need to be sent and every member can calculate them locally. This algorithm is known as LKH+. 