Information Security and Cryptography Research Group

On the Complexity of Breaking the Diffie-Hellman Protocol

Ueli Maurer and Stefan Wolf

Technical Report, no. 244, Institute for Theoretical Computer Science, ETH Zurich, Apr 1996.

It is shown that for a class of finite groups, breaking the Diffie-Hellman protocol is polynomial-time equivalent to computing discrete logarithms. Let G be a cyclic group with generator g and order jGj whose prime factorization is known. When for each large prime factor p of jGj an auxiliary group Hp defined over GF (p) with smooth order is given, then breaking the Diffie-Hellman protocol for G and computing discrete logarithms in G are polynomial-time equivalent. Possible auxiliary groups Hp are elliptic curves over GF (p) or over an extension field of GF (p), certain subgroups of the multiplicative group of such an extension field, and the Jacobian of a hyperelliptic curve. For a list of expressions in p, including p \Gamma 1, p + 1, and the cyclotomic polynomials of low degree in p, it is shown that an appropriate group Hp can efficiently be constructed if one of the expressions in the list is smooth. Furthermore, efficient constructions of Diffie-Hellman groups with provable equivalence are described.

BibTeX Citation

    author       = {Ueli Maurer and Stefan Wolf},
    title        = {On the Complexity of Breaking the {D}iffie-{H}ellman Protocol},
    number       = {244},
    series       = {Technical Report, Department of Computer Science, ETH Zuerich},
    year         = {1996},
    month        = {4},
    institution  = {Institute for Theoretical Computer Science, ETH Zurich},

Files and Links