A survey of key management for secure group communication <s> Centralized Flat Table <s> Introduction to the Theory of Boolean Functions and Circuits. The Minimimization of Boolean Functions. The Design of Efficient Circuits for Some Fundamental Functions. Asymptotic Results and Universal Circuits. Lower Bounds on Circuit Complexity. Monotone Circuits. Relations between Circuit Size, Formula Size and Depth. Formula Size. Circuits and other Non-Uniform Computation Methods vs. Turing Machines and other Uniform Computation Models. Hierarchies, Mass Production, and Reductions. Bounded-Depth Circuits. Synchronous, Planar, and Probabilistic Circuits. PRAMs and WRAMs: Parallel Random Access Machines. Branching Programs. References. Index. <s> BIB001 </s> A survey of key management for secure group communication <s> Centralized Flat Table <s> The Internet provides no support for privacy or authentication of multicast packets. However, an increasing number of applications require secure multicast services in order to restrict group membership and enforce accountability of group members. A major problem associated with the deployment of secure multicast delivery services is the scalability of the key distribution protocol. This is particularly true with regard to the handling of group membership changes, such as member departures and/or expulsions, which necessitate the distribution of a new session key to all the remaining group members. As the frequency of group membership changes increases, it becomes necessary to reduce the cost of key distribution operations. This paper explores the use of batching of group membership changes to reduce the frequency, and hence the cost, of key re-distribution operations. It focuses explicitly on the problem of cumulative member removal and presents an algorithm that minimizes the number of messages required to distribute new keys to the remaining group members. The algorithm is used in conjunction with a new multicast key management scheme which uses a set of auxiliary keys in order to improve scalability. In contrast to previous schemes which generate a fixed hierarchy of keys, the proposed scheme dynamically generates the most suitable key hierarchy by composing different keys. Our cumulative member removal algorithm uses Boolean function minimization techniques, and outperforms all other schemes known to us in terms of message complexity. <s> BIB002 </s> A survey of key management for secure group communication <s> Centralized Flat Table <s> Secure media broadcast over the Internet poses unique security challenges. One problem is access control to a large number of subscribers in a public broadcast. A common solution is to encrypt the broadcast data and to disclose the decryption key to legitimate receivers only. However, how do we securely and efficiently establish a shared secret among the legitimate receivers? And most importantly, how can we efficiently update the group key securely if receivers join or leave? How can we provide reliability for key update messages in a way that scales up to large groups? Recent research makes substantial progress to address these challenges. Current schemes feature efficient key update mechanisms assuming that the key updates are communicated reliably to the receivers. In practice, however the principal impediment to achieve a scalable system is to distribute the key updates reliably to all receivers. We have designed and implemented ELK, a novel key distribution protocol, to address these challenges with the following features: ELK features perfectly reliable, super-efficient member joins; ELK uses smaller key update messages than previous protocols; ELK features a mechanism that allows short hint messages to be used for key recovery allowing a tradeoff of communication overhead with member computation; ELK proposes to append a small amount of key update information to data packets, such that the majority of receivers can recover from lost key update messages; and ELK allows to trade off security with communication overhead. <s> BIB003
When a member leaves the group, all keys known by it are changed and the KDC sends out a rekey message containing Table II ). This way, every remaining member can update its old KEKs without gaining further knowledge about the KEKs other members had. A group from IBM proposed a similar scheme BIB002 ] to the one from the ETH group. Although the IBM proposal has the same properties as the flat table, they presented an optimisation for the number of messages needed for rekeying the group based on Boolean function minimisation techniques (BFM) BIB001 . In this case, rather than always sending a message containing the new TEK encrypted by each unchanged KEK, they apply the techniques and find the smallest set of KEKs needed to rekey all remaining members. This scheme is susceptible to collusion attacks. A set of evicted members, which have IDs with complementary bits, may combine their sets of keys to recover a valid set of keys, hence are able to have unauthorised access to group communication. BIB003 proposed the Efficient Large-group Key (ELK) protocol. The ELK protocol uses a hierarchical tree and is very similar to the OFT in the sense that a parent node key is generated from its children keys. ELK uses pseudo-random functions (PRFs) to build and manipulate the keys in the hierarchical tree. A PRF uses a key K on input M of length m to generate output of length n represented by the following notation: