skip to main content
article

Provably secure authenticated group Diffie-Hellman key exchange

Published: 01 July 2007 Publication History

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]
Agarwal, D., Chevassut, O., Thompson, M. R., and Tsudik, G. 2001. An integrated solution for secure group communication in wide-area networks. In Proc. of 6th IEEE Symposium on Computers and Communications. IEEE Computer Society Press, Washington, D.C. 22--28. Also Technical Report LBNL-47158, Lawrence Berkeley National Laboratory.
[2]
Amir, Y. and Stanton, J. 1998. The spread wide area group communication system. Tech. rep., CNDS-98-4.
[3]
Amir, Y., Kim, Y., Nita-Rotaru, C., Schultz, J., Stanton, J., and Tsudik, G. 2004. Secure group communication using robust contributory key agreement. IEEE Transactions on Parallel and Distributed Systems 15, 5 (May), 468--480.
[4]
Ateniese, G., Steiner, M., and Tsudik, G. 1998. Authenticated group key agreement and friends. In Proc. of ACM CCS '98. ACM Press, New York. 17--26.
[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]
Becker, K. and Wille, U. 1998. Communication complexity of group key distribution. In Proc. of ACM CCS '98. ACM Press, New York. 1--6.
[8]
Bellare, M. and Rogaway, P. 1993a. Entity authentication and key distribution. In Proc. of Crypto '93, D. R. Stinson, Ed. LNCS, vol. 773. Springer-Verlag, New York. 232--249.
[9]
Bellare, M. and Rogaway, P. 1993b. Random oracles are practical: A paradigm for designing efficient protocols. In Proc. of ACM CCS '93. ACM Press, New York. 62--73.
[10]
Bellare, M. and Rogaway, P. 1995. Provably secure session key distribution: The three party case. In Proc. of STOC '95. ACM Press, New York. 57--66.
[11]
Bellare, M., Canetti, R., and Krawczyk, H. 1996. Pseudo-random functions revisited: The cascade construction and its concrete security. In Proc. of FOCS '96. IEEE Computer Society Press, Washington, D.C. 514--523.
[12]
Bellare, M., Canetti, R., and Krawczyk, H. 1998. A modular approach to the design and analysis of authentication and key exchange protocols. In Proc. of STOC '98. ACM Press, New York. 419--428.
[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]
Berman, F., Fox, G., and Hey, T. 2003. Grid Computing: Making The Global Infrastructure a Reality. Wiley, New York.
[16]
Bird, R., Gopal, I. S., Herzberg, A., Janson, P. A., Kutten, S., Molva, R., and Yung, M. 1991. Systematic design of two-party authentication protocols. In Proc. of Crypto '91, J. Feigenbaum, Ed. LNCS, vol. 576. Springer-Verlag, New York. 44--61.
[17]
Birman, K. P. 1999. A review experience with reliable multicast. Software---Practice and Experience 29, 9 (July), 741--774.
[18]
Blake-Wilson, S. and Menezes, A. J. 1997a. Entity authentication and authenticated key transport protocols employing asymmetric techniques. In Proc. of SPW '97, B. Christianson, B. Crispo, T. M. A. Lomas, and M. Roe, Eds. LNCS, vol. 1361. Springer-Verlag, New York. 137--158.
[19]
Blake-Wilson, S., Johnson, D., and Menezes, A. J. 1997b. Key agreement protocols and their security analysis. In Proc. of 6th IMA International Conference on Cryptography and Coding, M. Darnell, Ed. LNCS, vol. 1355. Springer-Verlag, New York. 30--45.
[20]
Boneh, D. 1998. The decision Diffie-Hellman problem. In Proc. of ANTS III, J. P. Buhler, Ed. LNCS, vol. 1423. Springer-Verlag, New York. 48--63.
[21]
Boyd, C. 1995. Towards a classification of key agreement protocols. In Proc. of CSFW '95. IEEE Computer Society Press, Washington, D.C. 38--43.
[22]
Boyd, C. 1997. On key agreement and conference key agreement. In Workshop on Information Security and Privacy. LNCS, vol. 1270. Springer-Verlag, New York. 294--302.
[23]
Boyd, C. and Mathuria, A. 2003. Protocols for Authentication and Key Establishment. Springer-Verlag, New York.
[24]
Boyd, C. and Nieto, J. M. 2003. Round-optimal contributory conference key agreement. In Proc. of PKC '03, Y. G. Desmedt, Ed. LNCS, vol. 2567. Springer-Verlag, New York. 161--174.
[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]
Bresson, E., Chevassut, O., and Pointcheval, D. 2001a. Provably authenticated group Diffie-Hellman key exchange---the dynamic case. In Proc. of Asiacrypt '01, C. Boyd, Ed. LNCS, vol. 2248. Springer-Verlag, New York. 290--309. Full version available from authors' web pages.
[27]
Bresson, E., Chevassut, O., Pointcheval, D., and Quisquater, J.-J. 2001b. Provably authenticated group Diffie-Hellman key exchange. In Proc. of ACM CCS '01, P. Samarati, Ed. ACM Press, New York. 255--264.
[28]
Bresson, E., Chevassut, O., and Pointcheval, D. 2002a. Dynamic group Diffie-Hellman key exchange under standard assumptions. In Proc. of Eurocrypt '02, L. R. Knudsen, Ed. LNCS, vol. 2332. Springer-Verlag, New York. 321--336. Full version available from authors' web pages.
[29]
Bresson, E., Chevassut, O., and Pointcheval, D. 2002b. The group Diffie-Hellman problems. In Proc. of SAC '02, K. Nyberg and H. Heys, Eds. LNCS, vol. 2595. Springer-Verlag, New York. 325--338.
[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]
Cachin, C. and Strobl, R. 2004. Asynchronous group key exchange with failures. In Proc. of PODC '04. ACM Press, New York. 357--366.
[32]
Canetti, R. 2000. Security and composition of multi-party cryptographic protocols. J. of Cryptology 13, 1 (Winter), 143--202.
[33]
Canetti, R. and Krawczyk, H. 2001. Analysis of key-exchange protocols and their use for building secure channels. In Proc. of Eurocrypt '01, B. Pfitzmann, Ed. LNCS, vol. 2045. Springer-Verlag, New York. 453--474.
[34]
Canetti, R. and Krawczyk, H. 2002. Universally composable notions of key exchange and secure channels. In Proc. of Eurocrypt '02, L. R. Knudsen, Ed. LNCS, vol. 2332. Springer-Verlag, New York. 337--351.
[35]
Canetti, R., Goldreich, O., and Halevi, S. 1998. The random oracle methodology, revisited. In Proc. of STOC '98. ACM Press, New York. 209--218.
[36]
Chockler, G. V., Keidar, I., and Vitenberg, R. 2001. Group communication specifications: A comprehensive study. ACM Computing Surveys 33, 4 (Dec.), 427--469.
[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]
Diffie, W., van Oorschot, P. C., and Wiener, M. J. 1992. Authentication and authenticated key exchange. Designs, Codes and Cryptography 2, 2 (June), 107--125.
[40]
Dupont, R. and Enge, A. 2002. Practical non-interactive key distribution based on pairings. Cryptology ePrint Archive.
[41]
Foster, I. and Kesselman, C. 2004. The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Mateo, CA.
[42]
Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. J. Computer System Sciences 28, 2 (Apr.), 270--299.
[43]
Håstad, J. 1990. Pseudo-random generators under uniform assumptions. In Proc. of STOC '90. ACM Press, New York. 395--404.
[44]
Håstad, J., Impagliazzo, R., Levin, L. A., and Luby, M. 1999. A pseudo-random generator from any one-way function. SIAM J. Computing 28, 4 (Aug.), 1364--1396. Combination of {Impagliazzo et al. 1989} and {Håstad 1990}.
[45]
Impagliazzo, R., Levin, L. A., and Luby, M. 1989. Pseudo-random generation from one-way functions. In Proc. of STOC '89. ACM Press, New York. 12--24.
[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]
Joux, A. 2000. A one-round protocol for tripartite Diffie-Hellman. In Proc. of ANTS IV, W. Bosma, Ed. LNCS, vol. 1838. Springer-Verlag, New York. 385--394.
[48]
Joye, M. and Quisquater, J.-J. 1997. On the importance of securing your bins: The garbage-man-in-the-middle attack. In Proc. of ACM CCS '97. ACM Press, New York. 135--141.
[49]
Just, M. and Vaudenay, S. 1996. Authenticated multi-party key agreement. In Proc. of Asiacrypt '96, K. Kim and T. Matsumoto, Eds. LNCS, vol. 1163. Springer-Verlag, New York. 36--49.
[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]
Kim, Y., Perrig, A., and Tsudik, G. 2000. Simple and fault-tolerant key agreement for dynamic collaborative group. In Proc. of ACM CCS '00, S. Jajodia, Ed. ACM Press, New York. 235--244.
[52]
Kim, Y., Perrig, A., and Tsudik, G. 2001. Communication-efficient group key agreement. In Proc. of International Federation for Information Processing (IFIP SEC 2001), M. Dupuy and P. Paradinas, Eds. IFIP Conference Proceedings, vol. 193. International Federation for Information Processing. Kluwer, Boston, MA. 229--244.
[53]
Li, C.-H. and Pieprzyk, J. 1999. Conference key agreement from secret sharing. In Proc. of ACISP '99, J. Pieprzyk, R. Safavi-Naini, and J. Seberry, Eds. LNCS, vol. 1587. Springer-Verlag, New York. 64--76.
[54]
McGrew, D. A. and Sherman, A. T. 1998. Key establishment in large dynamic groups using one-way function trees. Manuscript.
[55]
Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A. 1997. Handbook of Applied Cryptography. CRC Press, Boca Raton, Florida. http://cacr.math.uwaterloo.ca/hac/.
[56]
Naor, M. and Reingold, O. 1997. Number-theoretic constructions of efficient pseudo-random functions. In Proc. of FOCS '97. IEEE Computer Society Press, Washington D.C. 458--467.
[57]
NIST. 1994. Federal Information Processing StandardsPublication 140-1: Security Requirements for Cryptographic Modules. U. S. National Institute of Standards and Technology.
[58]
Palmer, E. R., Smith, S. W., and Weingart, S. H. 1998. Using a high-performance, programmable secure coprocessor. In Proc. of Financial Crypto '98, R. Hirschfeld, Ed. LNCS, vol. 1465. Springer-Verlag, New York. 73--89.
[59]
Pereira, O. and Quisquater, J.-J. 2001. A security analysis of the cliques protocol suites. In Proc. of CSFW '01. IEEE Computer Society Press, Washington, D.C. 73--81.
[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]
Pfitzmann, B. and Waidner, M. 2001. A model for asynchronous reactive systems and its application to secure message transmission. In Proc. of the 22ndIEEE Symposium on Security and Privacy. IEEE Computer Society Press, Washington, D.C. 184--200.
[62]
Rodeh, O., Birman, K. P., and Dolev, D. 2001. The architecture and performance of the security protocols in the ensemble group communication system. ACM Trans. on Information and System Security 4, 3 (Aug.), 289--319.
[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]
Shoup, V. 2001. OAEP reconsidered. In Proc. of Crypto '01, J. Kilian, Ed. LNCS, vol. 2139. Springer-Verlag, New York. 239--259.
[66]
Steer, D. G., Strawczynski, L., Diffie, W., and Wiener, M. J. 1988. A secure audio teleconference system. In Proc. of Crypto '88, S. Goldwasser, Ed. LNCS, vol. 403. Springer-Verlag, New York. 520--528.
[67]
Steiner, M., Tsudik, G., and Waidner, M. 1996. Diffie-Hellman key distribution extended to group communication. In Proc. of ACM CCS '96. ACM Press, New York. 31--37.
[68]
Steiner, M., Tsudik, G., and Waidner, M. 2000. Key agreement in dynamic peer group. IEEE Transactions on Parallel and Distributed Systems 11, 8 (Aug.), 769--780.
[69]
Tzeng, W.-G. 2000. A practical and secure fault-tolerant conference-key agreement protocol. In Proc. of PKC '00, H. Imai and Y. Zheng, Eds. LNCS, vol. 1751. Springer-Verlag, New York. 1--13.
[70]
Vedder, K. and Weikmann, F. 1997. Smart cards requirements, properties, and applications. In State of the Art in Applied Cryptography, B. Preneel and V. Rijmen, Eds. LNCS, vol. 1528. Springer-Verlag, New York. 307--331.
[71]
von Renesse, R., Birman, K. P., Hayden, M., Vaysburd, A., and Karr, D. 1998. Building adaptive systems using ensemble. Software--Practice and Experience 28, 9 (Aug.), 963--979.
[72]
Weingart, S. H. 2000. Physical security devices for computer subsystems: A survey of attacks and defenses. In Proc. of CHES '00, ¸ C. K. Ko¸c and C. Paar, Eds. LNCS, vol. 1965. Springer-Verlag, New York. 302--317.

Cited By

View all
  • (2025)Blockchain-Based Decentralised Authentication in Closed EnvironmentsFuture Internet10.3390/fi1703009817:3(98)Online publication date: 21-Feb-2025
  • (2024)PATSIET Information Security10.1049/2024/75575142024Online publication date: 1-Jan-2024
  • (2023)An Access Control System Based on Blockchain with Zero-Knowledge Rollups in High-Traffic IoT EnvironmentsSensors10.3390/s2307344323:7(3443)Online publication date: 24-Mar-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Information and System Security
ACM Transactions on Information and System Security  Volume 10, Issue 3
July 2007
195 pages
ISSN:1094-9224
EISSN:1557-7406
DOI:10.1145/1266977
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2007
Published in TISSEC Volume 10, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Cryptography
  2. Diffie--Hellman
  3. Group Key Exchange

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)49
  • Downloads (Last 6 weeks)3
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Blockchain-Based Decentralised Authentication in Closed EnvironmentsFuture Internet10.3390/fi1703009817:3(98)Online publication date: 21-Feb-2025
  • (2024)PATSIET Information Security10.1049/2024/75575142024Online publication date: 1-Jan-2024
  • (2023)An Access Control System Based on Blockchain with Zero-Knowledge Rollups in High-Traffic IoT EnvironmentsSensors10.3390/s2307344323:7(3443)Online publication date: 24-Mar-2023
  • (2023)Security Verification of Low-Trust ArchitecturesProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616643(945-959)Online publication date: 15-Nov-2023
  • (2023)Electrocardiogram Based Group Device Pairing for WearablesIEEE Transactions on Mobile Computing10.1109/TMC.2022.320010422:11(6394-6409)Online publication date: 1-Nov-2023
  • (2023)Authenticated Distributed Group Key Agreement Protocol Using Elliptic Curve Secret Sharing SchemeIEEE Access10.1109/ACCESS.2023.327446811(45243-45254)Online publication date: 2023
  • (2023)A comprehensive survey on security, privacy issues and emerging defence technologies for UAVsJournal of Network and Computer Applications10.1016/j.jnca.2023.103607213:COnline publication date: 1-Apr-2023
  • (2023)Modelling Identity-Based Authentication and Key Exchange Protocol Using the Tamarin ProverInformation Security, Privacy and Digital Forensics10.1007/978-981-99-5091-1_9(107-122)Online publication date: 2-Nov-2023
  • (2023)A Secure Key Management on ODMRP in Mesh-Based Multicast NetworkComputational Intelligence for Engineering and Management Applications10.1007/978-981-19-8493-8_39(521-530)Online publication date: 30-Apr-2023
  • (2022)Member Tampering Attack on Burmester-Desmedt Group Key Exchange Protocol and Its CountermeasureMathematics10.3390/math1019368510:19(3685)Online publication date: 8-Oct-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media