Provably authenticated group Diffie-Hellman key exchange

ABSTRACT

Group Diffie-Hellman protocols for Authenticated Key Exchange (AKE) are designed to provide a pool of players with a shared secret key which may later be used, for example, to achieve multicast message integrity. Over the years, several schemes have been offered. However, no formal treatment for this cryptographic problem has ever been suggested. In this paper, we present a security model for this problem and use it to precisely define AKE (with "implicit" authentication) as the fundamental goal, and the entity-authentication goal as well. We then define in this model the execution of an authenticated group Diffie-Hellman scheme and prove its security.

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: G.Ateniese,M.Steiner,and G.Tsudik.New Multiparty Authentication Services and Key Agreement Protocols.Journal ofSelected Areas in Communications ,18(4):1 -13,IEEE,2000.
• 3: 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]
• 4: 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]
• 5: M.Bellare,D.Pointcheval,and P.Rogaway. Authenticated Key Exchange Secure Against Dictionary Attacks.In Proc.of Eurocrypt '00 ,vol. 1807 of LNCS ,pages 139 -155.Springer,2000.
• 6: 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
• 7: 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]
• 8: 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]
• 9: Eli Biham , Dan Boneh , Omer Reingold, Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring, Information Processing Letters, v.70 n.2, p.83-87, April 30, 1999 [doi>10.1016/S0020-0190(99)00047-2]
• 10: 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
• 11: Simon Blake-Wilson , Alfred Menezes, Authenticated Diffie-Hellman Key Agreement Protocols, Proceedings of the Selected Areas in Cryptography, p.339-361, August 17-18, 1998
• 12: Dan Boneh, The Decision Diffie-Hellman Problem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.48-63, June 21-25, 1998
• 13: M.Burmester and Y.Desmedt.A Secure and E .cient Conference Key Distribution System.In Proc of Eurocrypt '94 ,vol.950 of LNCS ,pages 275 -286. Springer,1995.
• 14: R.Canetti,J.Garay,G.Itkis,D.Micciancio, M.Naor,and B.Pinkas.Issues in Multicast Security: A Taxonomy and E .cient Constructions.In Proc.of INFOCOM '99 ,March 1999.
• 15: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 16: Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.229-235, August 20-24, 2000
• 17: W.Di .e and M.Hellman.New Directions In Cryptography.In IEEE Transactions on Information Theory ,vol.IT-22(6),pages 644 -654,November 1976.
• 18: 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
• 19: S.Goldwasser and S.Micali.Probabilisitic Encryption.Journal ofComputer and System Sciences ,28():270 -299,1984.
• 20: I.Ingemarsson,D.Tang,and C.Wong.A Conference Key Distribution System.In IEEE Transactions on Information Theory ,volume 28(5),pages 714 -720, September 1982.
• 21: 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
• 22: 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]
• 23: Alain Mayer , Moti Yung, Secure protocol transformation via “expansion”: from two-party to groups, Proceedings of the 6th ACM conference on Computer and communications security, p.83-92, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319721]
• 24: C.Meadows.Extending Formal Cryptographic Protocol Analysis Techniques for Group Protocols and Low-Level Cryptographic Primitives.In Workshop on Issues in the Theory ofSecurity (WITS '00),2000,.
• 25: 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
• 26: 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
• 27: A.Perrig.Simple and Fault-Tolerant Key Agreement for Dynamic Collaborative Groups.In International Workshop on Cryptographic Techniques and E-Commerce CrypTEC '99 ,1999.
• 28: D.Pointcheval and J.Stern.Security Arguments for Digital Signatures and Blind Signatures.J.of Cryptology ,13(3):361 -396,2000.
• 29: V.Shoup.Lower Bounds for Discrete Logarithms and Related Problems.In Proc.of Eurocrypt '97 ,vol.1233 of LNCS ,pages 256 --266.Springer,1997.
• 30: V.Shoup.On Formal Models for Secure Key Exchange.Technical report,IBM Zrich Research Lab, 1999.
• 31: 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]
• 32: 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:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Electronic data interchange (EDI)

General Terms:
Algorithms, Design, Security