Asynchronous group key exchange with failures

ABSTRACT

Group key exchange protocols allow a group of servers communicating over an asynchronous network of point-to-point links to establish a common key, such that an adversary which fully controls the network links (but not the group members) cannot learn the key. Currently known group key exchange protocols rely on the assumption that all group members participate in the protocol and if a single server crashes, then no server may terminate the protocol. In this paper, we propose the first purely asynchronous group key exchange protocol that tolerates a minority of servers to crash. Our solution uses a constant number of rounds, which makes it suitable for use in practice. Furthermore, we also investigate how to provide forward secrecy with respect to an adversary that may break into some servers and observe their internal state. We show that any group key exchange protocol among n servers that tolerates tc > 0 servers to crash can only provide forward secrecy if the adversary breaks into less than n - 2tc servers, and propose a group key exchange protocol that achieves this bound.

REFERENCES

• 1: Yair Amir , Yongdae Kim , Cristina Nita-Rotaru , John L. Schultz , Jonathan Stanton , Gene Tsudik, Secure Group Communication Using Robust Contributory Key Agreement, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.468-480, May 2004 [doi>10.1109/TPDS.2004.1278104]
• 2: Exploring Robustness in Group Key Agreement, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.399, April 16-19, 2001
• 3: G. Ateniese, M. Steiner, and G. Tsudik, "New multiparty authentication services and key agreement protocols," Journal of Selected Areas in Communications IEEE, vol. 18, no. 4, pp. 1--13, 2000.
• 4: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 5: M. Bellare, D. Pointcheval, and P. Rogaway, "Authenticated key exchange secure against dictionary attacks," in Advances in Cryptology: Eurocrypt '00, 2000.
• 6: Colin Boyd, On Key Agreement and Conference Key Agreement, Proceedings of the Second Australasian Conference on Information Security and Privacy, p.294-302, July 07-09, 1997
• 7: 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]
• 8: M. Burmester and Y. Desmedt, "A secure and efficient conference key distribution system," in Advances in Cryptology: Eurocrypt '94, 1994.
• 9: Christian Cachin , Klaus Kursawe , Frank Petzold , Victor Shoup, Secure and Efficient Asynchronous Broadcast Protocols, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.524-541, August 19-23, 2001
• 10: Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343531]
• 11: Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
• 12: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 13: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 14: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 15: Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001 [doi>10.1145/503112.503113]
• 16: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 17: S. Goldwasser and S. Micali, "Probabilistic encryption," Journal of Computer and System Sciences, vol. 28, pp. 270--299, 1984.
• 18: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 19: I. Ingemarasson, D. Tang, and C. Wong, "A conference key distribution system," IEEE Transactions on Information Theory, vol. 28, no. 5, pp. 714--720, 1982.
• 20: Mike Just , Serge Vaudenay, Authenticated Multi-Party Key Agreement, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.36-49, November 03-07, 1996
• 21: J. Katz and M. Yung, "Scalable protocols for authenticated group key exchange," in Advances in Cryptology: Crypto'03, 2003.
• 22: Jesper Buus Nielsen, A Threshold Pseudorandom Function Construction and Its Applications, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.401-416, August 18-22, 2002
• 23: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 24: Ohad Rodeh , Kenneth P. Birman , Danny Dolev, A Study of Group Rekeying, Cornell University, Ithaca, NY, 2000
• 25: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 26: 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]
• 27: M. Steiner, Secure Group Key Agreement. PhD thesis, Naturwissenschaftlich- Technische Fakultät der Universität des Saarlandes, Saarbrücken, March 2002.
• 28: Wen-Guey Tzeng, A Practical and Secure-Fault-Tolerant Conferenc-Key Agreement Protocol, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.1-13, January 18-20, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Reliability, Security

Keywords:
group communication, group key exchange, provable security, universal composability