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
-
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},
url = {https://eprint.iacr.org/1997/014}
}
