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

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 module 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 (1985). (C) 1999 Elsevier Science B.V. All rights reserved.