id: 01771670
dt: j
an: 01771670
au: Biham, Eli; Boneh, Dan; Reingold, Omer
ti: Breaking generalized Diffie-Hellman modulo a composite is no easier than
    factoring.
so: Inf. Process. Lett. 70, No.2, 83-87 (1999).
py: 1999
pu: Elsevier Sciences Publishers (North-Holland), Amsterdam
la: EN
cc: 
ut: generalized Diffie-Hellman assumption; factorization algorithm; Blum
    integers
ci: Zbl 0922.68052
li: doi:10.1016/S0020-0190(99)00047-2
ab: Summary: 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). {\it M. Naor} and {\it O. Reingold} [J.
    Comput. Syst. Sci. 58, 336-375 (1999; Zbl 0922.68052)] 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 strengthens a previous
    “worst-case" reduction of Shmuely (1985).
rv: