# On the Complexity of Breaking the {D}iffie-{H}ellman 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.