Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-061 | 12th November 1997 00:00

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

RSS-Feed




TR97-061
Authors: Eli Biham, Dan Boneh, Omer Reingold
Publication: 26th December 1997 18:37
Downloads: 932
Keywords: 


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.



ISSN 1433-8092 | Imprint