Paper 1997/014

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

Eli Biham, Dan Boneh, and Omer Reingold

Abstract

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.

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

BibTeX

@misc{cryptoeprint:1997/014,
      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{https://eprint.iacr.org/1997/014}},
      url = {https://eprint.iacr.org/1997/014}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.