Paper 1997/014

Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

Eli Biham, Dan Boneh, and Omer Reingold


The Diffie-Hellman key-exchange protocol may naturally be extended to k>2 parties. This gives rise to the generalized Diffie-Hellman assumption (GDH-Assumption). Naor and Reingold have recently shown an efficient construction of pseudo-random functions and reduced the security of their construction to the GDH-Assumption. In this note, we prove that breaking this assumption modulo a composite would imply an efficient algorithm for factorization. Therefore, the security of both the key-exchange protocol and the pseudo-random functions can be reduced to factoring.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Diffie-Hellman AssumptionFactoringKey-ExchangePseudo-Random Function.
Contact author(s)
reingold @ wisdom weizmann ac il
1997-11-09: received
Short URL
Creative Commons Attribution


      author = {Eli Biham and Dan Boneh and Omer Reingold},
      title = {Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 1997/014},
      year = {1997},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.