# Towards the Equivalence of Breaking the {D}iffie-{H}ellman Protocol and Computing Discrete Logarithms

## Ueli Maurer

```
```Let $G$ be an arbitrary cyclic group with generator $g$ and order $|G|$
with known factorization. $G$ could be the subgroup generated by $g$
within a larger group $H$. Based on an assumption about the existence
of smooth numbers in short intervals, we prove that breaking the
Diffie-Hellman protocol for $G$ and base $g$ is equivalent to computing
discrete logarithms in $G$ to the base $g$ when a certain side
information string $S$ of length $2\log|G|$ is given, where $S$ depends
only on $|G|$ but not on the definition of $G$ and appears to be of no
help for computing discrete logarithms in $G$. If every prime factor
$p$ of $|G|$ is such that one of a list of expressions in $p$,
including $p-1$ and $p+1$, is smooth for an appropriate smoothness
bound, then $S$ can efficiently be constructed and therefore breaking
the Diffie-Hellman protocol is equivalent to computing discrete
logarithms.