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

Authors: E. Biham, D. Boneh, and O. Reingold

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.

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

Full paper: gzipped-PostScript