Information Security and Cryptography Research Group

Diffie-Hellman, Decision Diffie-Hellman, and Discrete Logarithms

Ueli Maurer and Stefan Wolf

Let $G$ be a cyclic group of order $n$. With respect to polynomial-time non-uniform generic reductions, the Diffie-Hellman problem and the discrete logarithm problem are equivalent in $G$ if and only if $n$ contains no multiple large prime factors. The Diffie-Hellman decision problem is equivalent to the Diffie-Hellman problem in $G$ if and only if all prime factors of $n$ are small.

BibTeX Citation

@inproceedings{MauWol98c,
    author       = {Ueli Maurer and Stefan Wolf},
    title        = {{D}iffie-{H}ellman, {D}ecision {D}iffie-{H}ellman, and Discrete Logarithms},
    booktitle    = {IEEE International Symposium on Information Theory --- ISIT~'98},
    pages        = {327},
    year         = {1998},
    month        = {8},
    publisher    = {IEEE},
}

Files and Links

• PDF
• PS