Robust group key agreement using short broadcasts

ABSTRACT

A group key agreement protocol (GKA) allows a set of players to establish a shared secret key which can be used to secure a subsequent communication. Several efficient constant-round GKA's have been proposed. However, their performance degrades if some players fail during protocol execution. This is a problem in practice, e.g. for mobile nodes communicating over wireless media, which can loose connectivity during the protocol execution. Current constant-round GKA protocols are either efficient and non-robust or robust but not efficient: Assuming a reliable broadcast communication medium, the standard encryption-based group key agreement protocol can be robust against arbitrary number of node faults, but the size of the messages broadcast by every player is proportional to the number of players. In contrast, non-robust group key agreement can be achieved with each player broadcasting just constant-sized messages.

We propose a novel 2-round group key agreement protocol which tolerates up to T node failures using O(T)-sized messages, for any T. To exemplify the usefulness of this flexible trade-off between message size and fault tolerance, we show that the new protocol implies a fully-robust group key agreement with O(log n)-sized messages and expected round complexity close to 2, assuming random node faults. The proposed protocol is secure under the (standard) Decisional Square Diffie-Hellman assumption.

REFERENCES

• 1: Exploring Robustness in Group Key Agreement, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.399, April 16-19, 2001
• 2: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 3: Emmanuel Bresson , Olivier Chevassut , David Pointcheval , Jean-Jacques Quisquater, Provably authenticated group Diffie-Hellman key exchange, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502018]
• 4: M, Burmester and Y, Desmedt. A secure and efficient conference key distribution system. In Advances in Cryptology - EUROCRYPT 1994, 1994.
• 5: Christian Cachin , Reto Strobl, Asynchronous group key exchange with failures, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011820]
• 6: Jonathan Katz , Moti Yung, Scalable Protocols for Authenticated Group Key Exchange, Journal of Cryptology, v.20 n.1, p.85-113, January 2007 [doi>10.1007/s00145-006-0361-5]
• 7: Group Key Agreement Efficient in Communication, IEEE Transactions on Computers, v.53 n.7, p.905-921, July 2004 [doi>10.1109/TC.2004.31]
• 8: D. G. Steer , L. Strawczynski , Whitfield Diffie , Michael J. Wiener, A Secure Audio Teleconference System, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.520-528, August 21-25, 1988
• 9: Michael Steiner , Gene Tsudik , Michael Waidner, Key Agreement in Dynamic Peer Groups, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.769-780, August 2000 [doi>10.1109/71.877936]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Reliability, Security

Keywords:
fault tolerance, group key agreement