Secure group communications using key graphs

Many emerging network applications (e.g., teleconference, information servi ces, distributed interactive simulation, and collaborative work) are based upon a group communications model. As a result, securing group communicatio ns, i.e., providing confidentiality, authenticity, and integrity of message s delivered between group members, will become a critical networking issue. We present, in this paper, a novel solution to the scalability problem of group/multicast key management. We formalize the notion of a secure group a s a triple (U, K, R) where U denotes a set of users, K a set of keys held b y the users, and R a user-key relation. We then introduce key graphs to spe cify secure groups. For a special class of key graphs, we present three str ategies for securely distributing rekey messages after a join/leave and spe cify protocols for joining and leaving a secure group. The rekeying: strate gies and join/leave protocols are implemented in a prototype key server we have built. We present measurement results from experiments and discuss per formance comparisons. We show that our group key management service, using any of the three rekeying strategies, is scalable to large groups with freq uent joins and leaves. In particular, the average measured processing time per join/leave increases linearly with the logarithm of group size.