On the Complexity of Breaking the Diffie-Hellman Protocol
Ueli Maurer and Stefan Wolf
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
@techreport{MauWol96d,
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},
}