International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Eli Biham
Dan Boneh
Omer Reingold
Download:
URL: http://eprint.iacr.org/1997/014
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1997-11296,
  title={Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring},
  booktitle={IACR Eprint archive},
  keywords={Diffie-Hellman Assumption, Factoring, Key-Exchange, Pseudo-Random Function.},
  url={http://eprint.iacr.org/1997/014},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. reingold@wisdom.weizmann.ac.il 10500 received Nov 9th, 1997.},
  author={Eli Biham and Dan Boneh and Omer Reingold},
  year=1997
}