# Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring

**Authors:**

*E. Biham, D. Boneh, and O. 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 proved its security based on the
GDH-Assumption.
In this note, we prove that breaking this assumption modulo a so called
Blum-integer would imply an efficient algorithm for factorization.
Therefore, both the key-exchange protocol and the pseudo-random
functions
are secure as long as factoring Blum-integers is hard.
Our reduction strengthen a previous ``worst-case'' reduction of
Shmuely.

** Reference:**

In *Information Processing Letters* (IPL), Vol. 70, 1999, pp. 83--87

**Full paper:**
gzipped-PostScript