A survey of key management for secure group communication <s> One-way Function Tree <s> We present, implement, and analyze a new scalable centralized algorithm, called OFT, for establishing shared cryptographic keys in large, dynamically changing groups. Our algorithm is based on a novel application of one-way function trees. In comparison with the top-down logical key hierarchy (LKH) method of Wallner et al., our bottom-up algorithm approximately halves the number of bits that need to be broadcast to members in order to rekey after a member is added or evicted. The number of keys stored by group members, the number of keys broadcast to the group when new members are added or evicted, and the computational efforts of group members, are logarithmic in the number of group members. Among the hierarchical methods, OFT is the first to achieve an approximate halving in broadcast length, an idea on which subsequent algorithms have built. Our algorithm provides complete forward and backward security: Newly admitted group members cannot read previous messages, and evicted members cannot read future messages, even with collusion by arbitrarily many evicted members. In addition, and unlike LKH, our algorithm has the option of being member contributory in that members can be allowed to contribute entropy to the group key. Running on a Pentium II, our prototype has handled groups with up to 10 million members. This algorithm offers a new scalable method for establishing group session keys for secure large-group applications such as broadcast encryption, electronic conferences, multicast sessions, and military command and control. <s> BIB001 </s> A survey of key management for secure group communication <s> One-way Function Tree <s> Multicast communication is becoming the basis for a growing number of applications. It is therefore critical to provide sound security mechanisms for multicast communication. Yet, existing security protocols for multicast offer only partial solutions. We first present a taxonomy of multicast scenarios on the Internet and point out relevant security concerns. Next we address two major security problems of multicast communication: source authentication, and key revocation. Maintaining authenticity in multicast protocols is a much more complex problem than for unicast; in particular, known solutions are prohibitively inefficient in many cases. We present a solution that is reasonable for a range of scenarios. This approach can be regarded as a 'midpoint' between traditional message authentication codes and digital signatures. We also present an improved solution to the key revocation problem. <s> BIB002
An improvement in the hierarchical binary tree approach is a one-way function tree (OFT) and was proposed by BIB001 . Their scheme reduces the size of the rekeying message from 2 · (log 2 n) to only (log 2 n). Here a node's KEK is generated rather than just attributed. The KEKs held by a node's children are blinded using a one-way function and then mixed together using a mixing function. The result of this mixing function is the KEK held by the node. This is represented by the following formula: Where left(i) and right(i) denote respectively the left and right children of node i. The function g is one-way, and f is a mixing function: Ancestors of a node are those nodes in the path from its parent node to the root. In this article, the set of ancestor of a node is called ancestor set and the set of siblings of the nodes in ancestor set are called sibling set (see Figure 4) . Each member receives the key (associated to its leaf node), its sibling's blinded key and the blinded keys corresponding to each node in its sibling set. For a balanced tree, each member stores l og 2 n + 1 keys. For example, in Figure 4 , member u 4 knows key k 4 and blinded keys k plying this information to the formula 1, member u 4 is able to generate all keys in its ancestor set (k 34 , k 14 and k). The message size reduction is achieved because in the standard scheme, when a node's key changes, the new key must be encrypted with its two children's keys, and in the OFT scheme, the blinded key changed in a node has to be encrypted only with the key of its sibling node. Figure 5 shows an example of this scheme. Member u 3 joins the group at node n 34 . It requires keys k 34 , k 14 and k to be changed. The only values that must be transmitted are the blinded KEKs k Each is respectively encrypted with k 4 , k 12 and k 58 . The new KEKs can be calculated by every group member: BIB002 proposed a slightly different approach that achieves the same communication overhead. Their scheme uses a pseudo-random-generator  ] to generate the new KEKs rather than a one-way function and it is applied only on users removal. This scheme is known as the one-way function chain tree. The pseudo-random-generator, G(x), doubles the size of its input (x), and there are two functions, L(x) and R(x), that represent the left and right halves of the output of where |L(x)| = |R(x)| = |x|). When a user u leaves the group, the algorithm to rekey the tree goes as follows: