ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

{D}iffie-{H}ellman, {D}ecision {D}iffie-{H}ellman, 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.