Provably secure authenticated group Diffie-Hellman key exchange

ABSTRACT

Authenticated key-exchange protocols allow two participants A and B, communicating over a public network and each holding an authentication means to exchange a shared secret value. Methods designed to deal with this cryptographic problem ensure A (resp. B) that no other participants aside from B (resp. A) can learn any information about the agreed value and often also ensure A and B that their respective partner has actually computed this value. A natural extension to this cryptographic method is to consider a pool of participants exchanging a shared secret value and to provide a formal treatment for it. Starting from the famous two-party Diffie--Hellman (DH) key-exchange protocol and from its authenticated variants, security experts have extended it to the multiparty setting for over a decade and, in the past few years, completed a formal analysis in the framework of modern cryptography. The present paper synthesizes this body of work on the provably-secure authenticated group DH key exchange.

REFERENCES

• 1: An Integrated Solution for Secure Group Communication in Wide-Area Networks, Proceedings of the Sixth IEEE Symposium on Computers and Communications, p.22, July 03-05, 2001
• 2: Amir, Y. and Stanton, J. 1998. The spread wide area group communication system. Tech. rep., CNDS-98-4.
• 3: 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]
• 4: Giuseppe Ateniese , Michael Steiner , Gene Tsudik, Authenticated group key agreement and friends, Proceedings of the 5th ACM conference on Computer and communications security, p.17-26, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288097]
• 5: Ateniese, G., Steiner, M., and Tsudik, G. 2000. New multi-party authentication services and key agreement protocols. IEEE Journal of Selected Areas in Communications 18, 4 (Apr.), 628--639.
• 6: Backes, M. and Cachin, C. 2003. Reliable broadcast in a computational hybrid model with byzantine faults, crashes, and recoveries. In Proc. of Intl. Conference on Dependable Systems and Networks (DSN-2003). 37--46.
• 7: Klaus Becker , Uta Wille, Communication complexity of group key distribution, Proceedings of the 5th ACM conference on Computer and communications security, p.1-6, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288094]
• 8: Mihir Bellare , Phillip Rogaway, Entity authentication and key distribution, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.232-249, January 1994, Santa Barbara, California, United States
• 9: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 10: Mihir Bellare , Phillip Rogaway, Provably secure session key distribution: the three party case, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.57-66, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225084]
• 11: M. Bellare , R. Canetti , H. Krawczyk, Pseudorandom functions revisited: the cascade construction and its concrete security, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.514, October 14-16, 1996
• 12: Mihir Bellare , Ran Canetti , Hugo Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.419-428, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276854]
• 13: Bellare, M., Pointcheval, D., and Rogaway, P. 2000. Authenticated key exchange secure against dictionary attacks. In Proc. of Eurocrypt '00, B. Preneel, Ed. LNCS, vol. 1807. Springer-Verlag, New York. 139--155.
• 14: Berket, K., Agarwal, D., and Chevassut, O. 2002. A practical approach to the intergroup protocols. Future Generation Computer Systems 18, 5 (Apr.), 709--719.
• 15: Fran Berman , Geoffrey Fox , Anthony J. G. Hey , Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons, Inc., New York, NY, 2003
• 16: Ray Bird , Inder S. Gopal , Amir Herzberg , Philippe A. Janson , Shay Kutten , Refik Molva , Moti Yung, Systematic Design of Two-Party Authentication Protocols, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.44-61, August 11-15, 1991
• 17: Kenneth P. Briman, A review of experiences with reliable multicast, Software—Practice & Experience, v.29 n.9, p.741-774, July 25, 1999 [doi>10.1002/(SICI)1097-024X(19990725)29:9<741::AID-SPE259>3.0.CO;2-I]
• 18: Simon Blake-Wilson , Alfred Menezes, Entity Authentication and Authenticated Key Transport Protocols Employing Asymmetric Techniques, Proceedings of the 5th International Workshop on Security Protocols, p.137-158, April 07-09, 1997
• 19: Simon Blake-Wilson , Don Johnson , Alfred Menezes, Key Agreement Protocols and Their Security Analysis, Proceedings of the 6th IMA International Conference on Cryptography and Coding, p.30-45, December 17-19, 1997
• 20: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 21: C. Boyd, Towards a classification of key agreement protocols, Proceedings of the 8th IEEE workshop on Computer Security Foundations, p.38, March 13-15, 1995
• 22: 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
• 23: Colin A. Boyd , Anish Mathuria, Protocols for Key Establishment and Authentication, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 24: Colin Boyd , Juan Manuel González Nieto, Round-Optimal Contributory Conference Key Agreement, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.161-174, January 06-08, 2003
• 25: Bresson, E. and Catalano, D. 2004. Constant round authenticated group key agreement via distributed computation. In Proc. of PKC '04, F. Bao, R. H. Deng, and J. Zhou, Eds. LNCS, vol. 2947. Springer-Verlag, New York. 115--129.
• 26: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Provably Authenticated Group Diffie-Hellman Key Exchange - The Dynamic Case, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.290-309, December 09-13, 2001
• 27: 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]
• 28: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, Dynamic Group Diffie-Hellman Key Exchange under Standard Assumptions, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.321-336, May 02, 2002
• 29: Emmanuel Bresson , Olivier Chevassut , David Pointcheval, The Group Diffie-Hellman Problems, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.325-338, August 15-16, 2002
• 30: Burmester, M. and Desmedt, Y. G. 1994. A secure and efficient conference key distribution system. In Proc. of Eurocrypt '94, A. D. Santis, Ed. LNCS, vol. 950. Springer-Verlag, New York. 275--286.
• 31: 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]
• 32: Canetti, R. 2000. Security and composition of multi-party cryptographic protocols. J. of Cryptology 13, 1 (Winter), 143--202.
• 33: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 34: Ran Canetti , Hugo Krawczyk, Universally Composable Notions of Key Exchange and Secure Channels, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.337-351, May 02, 2002
• 35: Ran Canetti , Oded Goldreich , Shai Halevi, The random oracle methodology, revisited (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.209-218, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276741]
• 36: 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]
• 37: Crescenzo, G. D., Ferguson, N., Impagliazzo, R., and Jakobsson, M. 1999. How to forget a secret. In Proc. of STACS '99, C. Meinel and S. Tison, Eds. LNCS, vol. 1563. Springer-Verlag, New York. 500--509.
• 38: Diffie, W. and Hellman, M. E. 1976. New directions in cryptography. IEEE Trans. on Information Theory IT-22, 6 (Nov.), 644--654.
• 39: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 40: Dupont, R. and Enge, A. 2002. Practical non-interactive key distribution based on pairings. Cryptology ePrint Archive.
• 41: Ian Foster , Carl Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 42: Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. J. Computer System Sciences 28, 2 (Apr.), 270--299.
• 43: J. Håstad, Pseudo-random generators under uniform assumptions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.395-404, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100270]
• 44: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 45: R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
• 46: Ingemarsson, I., Tang, D. T., and Wong, C. K. 1982. A conference key distribution system. IEEE Trans. on Information Theory IT-28, 5 (Sep.), 714--720.
• 47: Antoine Joux, A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.385-394, July 02-07, 2000
• 48: Marc Joye , Jean-Jacques Quisquater, On the importance of securing your bins: the garbage-man-in-the-middle attack, Proceedings of the 4th ACM conference on Computer and communications security, p.135-141, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266449]
• 49: 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
• 50: Katz, J. and Yung, M. 2003. Scalable protocols for authenticated group key exchange. In Proc. of Crypto '03, D. Boneh, Ed. LNCS, vol. 2729. Springer-Verlag, New York. 110--125.
• 51: Yongdae Kim , Adrian Perrig , Gene Tsudik, Simple and fault-tolerant key agreement for dynamic collaborative groups, Proceedings of the 7th ACM conference on Computer and communications security, p.235-244, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352638]
• 52: Yongdae Kim , Adrian Perrig , Gene Tsudik, Communication-Efficient Group Key Agreement, Proceedings of the IFIP TC11 Sixteenth Annual Working Conference on Information Security: Trusted Information: The New Decade Challenge, p.229-244, June 11-13, 2001
• 53: Chih-Hung Li , Josef Pieprzyk, Conference Key Agreement from Secret Sharing, Proceedings of the 4th Australasian Conference on Information Security and Privacy, p.64-76, April 07-09, 1999
• 54: McGrew, D. A. and Sherman, A. T. 1998. Key establishment in large dynamic groups using one-way function trees. Manuscript.
• 55: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 56: M. Naor , O. Reingold, Number-theoretic constructions of efficient pseudo-random functions, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.458, October 19-22, 1997
• 57: NIST. 1994. Federal Information Processing StandardsPublication 140-1: Security Requirements for Cryptographic Modules. U. S. National Institute of Standards and Technology.
• 58: Sean W. Smith , Elaine R. Palmer , Steve Weingart, Using a High-Performance, Programmable Secure Coprocessor, Proceedings of the Second International Conference on Financial Cryptography, p.73-89, February 23-25, 1998
• 59: Olivier Pereira , Jean-Jacques Quisquater, A Security Analysis of the Cliques Protocols Suites, Proceedings of the 14th IEEE workshop on Computer Security Foundations, p.73, June 11-13, 2001
• 60: Perrig, A. 1999. Simple and fault-tolerant key agreement for dynamic collaborative groups. In International Workshop on Cryptographic Techniques and E-Commerce CrypTEC '99. Hong-Kong City University Press, Hong-Kong.
• 61: 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
• 62: The architecture and performance of security protocols in the ensemble group communication system: Using diamonds to guard the castle, ACM Transactions on Information and System Security (TISSEC), v.4 n.3, p.289-319, August 2001 [doi>10.1145/501978.501982]
• 63: Rubin, A. D. and Shoup, V. 1996. Session-key distribution using smart cards. In Proc. of Eurocrypt '96, U. M. Maurer, Ed. LNCS, vol. 1070. Springer-Verlag, New York. 321--331.
• 64: Shoup, V. 1999. On formal models for secure key exchange. Technical Report RZ 3120, IBM Zürich Research Lab, Zürich, CH. November.
• 65: Victor Shoup, OAEP Reconsidered, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.239-259, August 19-23, 2001
• 66: D. G. Steer , L. Strawczynski , W. Diffie , M. Wiener, A secure audio teleconference system, Proceedings on Advances in cryptology, p.520-528, February 1990, Santa Barbara, California, United States
• 67: Michael Steiner , Gene Tsudik , Michael Waidner, Diffie-Hellman key distribution extended to group communication, Proceedings of the 3rd ACM conference on Computer and communications security, p.31-37, March 14-15, 1996, New Delhi, India [doi>10.1145/238168.238182]
• 68: 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]
• 69: 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
• 70: Klaus Vedder , Franz Weikmann, Smart Cards - Requirements, Properties, and Applications, State of the Art in Applied Cryptography, Course on Computer Security and Industrial Cryptography - Revised Lectures, p.307-331, June 03-06, 1997
• 71: Robbert van Renesse , Ken Birman , Mark Hayden , Alexey Vaysburd , David Karr, Building adaptive systems using ensemble, Software—Practice & Experience, v.28 n.9, p.963-979, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<963::AID-SPE179>3.0.CO;2-9]
• 72: Steve H. Weingart, Physical Security Devices for Computer Subsystems: A Survey of Attacks and Defences, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.302-317, August 17-18, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Security

Keywords:
Cryptography, Diffie--Hellman, Group Key Exchange