Postscript document

Introduction

 

The proliferation of applications, protocols and services that rely on group communication prompts the need for group-oriented security mechanisms (in addition to the traditional requirements of fault-tolerance, scalability, and reliability). Current group-oriented applications include IP telephony, video conferencing, collaborative workspaces, interactive chats and multi-user games. The security requirements of these applications are fairly typical, e.g., confidentiality, data integrity, authentication and access control. These are achieved through some form of group key management.

The peer nature of many group applications results in certain unique properties and requirements. First, every member in a peer group is both a sender and a receiver. Second, peer groups tend to be small, with fewer than a hundred members. Also, peer groups have no hierarchy and all members enjoy the same status. Therefore, solutions that assign greater importance to some group members are undesirable, since privileged members might behave maliciously; they are also attractive targets of attacks. This essentially rules out the traditional key distribution paradigm as it calls for higher trust in the group member who generates and distributes keys. Finally, since all networks are prone to faults and congestion, any subset of group members must be prepared to function as a group in its own right. In other words, if a network partition splits the members into multiple subgroups, each subgroup must quickly recover and continue to function independently.

In the last two decades a lot of research has been conducted with the aim of minimizing cryptographic overhead in security protocols. It has been long held as an incontrovertible fact that heavy-weight computation - such as large number arithmetic which is the basis of many modern cryptographic algorithms - is the greatest burden imposed by security protocols. We believe that, although this has been the case in the past, rapid advances in computing have resulted in drastic improvements in large-number arithmetic computations. For example, three years ago, a top-of-the-line RISC workstation performed a $512$-bit modular exponentiation in around $24$ ms. Today, an $850$ Mhz Pentium III PC (priced at $1/5$-th of the old RISC workstation) performs the same operation in under $1$ ms.

In contrast, communication latency has not improved appreciably. Network devices and communication lines have become significantly faster and cheaper. However, the communication (especially via the Internet) has become both accessible and affordable which resulted in drastic increase in the demand for network bandwidth. Consequently, the explosion in the number of users and their devices often causes network congestion and outages. Moreover, while computation power and bandwidth are increasing, network delay is still faced with a fundamental limit dictated by the speed of light.

The bottleneck shift from computation to communication latency leads us to start looking at cryptographic protocols in a different light: allowing more liberal use of cryptographic operations while attempting to reduce the communication overhead. The latter includes both round and message complexity. Communication overhead is especially relevant in a peer group setting since group members can be spread throughout a large network, e.g., the global Internet.

We consider a protocol suggested by Steer et al.in 1988 [SSDW88], one of the first group key agreement protocols. Their protocol is based on the Diffie-Hellman key exchange and assumes the formation of a secure static group. We extend their protocol to deal with dynamic groups and network failures. This protocol - referred to as STR hereafter - was neglected due to its heavy computation and communication requirements: $O(n)$ communication rounds and $O(n)$ cryptographic operations are necessary to establish a shared key in a group of $n$ members. However, we extend STR and construct new communication-efficient protocols that support dynamic groups. More concretely, we construct an entire group key management protocol suite, that is particularly efficient in a WAN environment where moderate to high network delays dominate. An extended version of this paper that provides more detail of our algorithms and security is available from the authors.