### 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.

Available format(s)
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
Short URL
https://ia.cr/1997/014

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.