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