# The Relationship Between Breaking the {D}iffie-{H}ellman Protocol and Computing Discrete Logarithms

## Ueli Maurer and Stefan Wolf

```
```Both uniform and non-uniform results concerning the
security of the Diffie-Hellman key-exchange protocol
are proved. First, it is shown that in a cyclic group G
of order |G|=prod(p_i^e_i), where all the multiple
prime factors of |G| are polynomial in log|G|, there
exists an algorithm that reduces the computation of
discrete logarithms in G to breaking the Diffie-Hellman
protocol in G and has complexity
sqrt{max{nu(p_i)}}*(log|G|)^O(1), where nu(p) stands
for the minimum of the set of largest prime factors of
all the numbers d in the interval [p-2 sqrt p+1 , p+2
sqrt p+1]. Under the unproven but plausible assumption
that nu(p) is polynomial in log p, this reduction
implies that the Diffie-Hellman problem and the
discrete logarithm problem are polynomial-time
equivalent in G. Second, it is proved that the
Diffie-Hellman problem and the discrete logarithm
problem are equivalent in a uniform sense for groups
whose orders belong to certain classes: there exists a
polynomial-time reduction algorithm that works for all
those groups. Moreover, it is shown that breaking the
Diffie-Hellman protocol for a small but non-negligible
fraction of the instances is equally difficult as
breaking it for all instances. Finally, efficient
constructions of groups are described for which the
algorithm reducing the discrete logarithm problem to
the Diffie-Hellman problem is efficiently constructible.