Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms

Ueli Maurer

Advances in Cryptology — CRYPTO '94, Lecture Notes in Computer Science, Springer-Verlag, vol. 839, pp. 271–281, Aug 1994.

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.

BibTeX Citation

@inproceedings{Maurer94,
    author       = {Ueli Maurer},
    title        = {Towards the Equivalence of Breaking the {D}iffie-{H}ellman Protocol and Computing Discrete Logarithms},
    editor       = {Yvo Desmedt},
    booktitle    = {Advances in Cryptology --- CRYPTO~'94},
    pages        = {271--281},
    series       = {Lecture Notes in Computer Science},
    volume       = {839},
    year         = {1994},
    month        = {8},
    publisher    = {Springer-Verlag},
}