Cryptology ePrint Archive: Report 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.
Category / Keywords: Diffie-Hellman Assumption, Factoring, Key-Exchange, Pseudo-Random Function.
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: received Nov 9th, 1997.
Contact author: reingold at wisdom weizmann ac il
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]