3
$\begingroup$

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?

Is there any group for which we suspect them to be different?

Could there be a finite list of groups where if Diffie Hellman problem and the Discrete Log are equivalent then Diffie Hellman problem and the Discrete Log are equivalent over any group they can be defined?

$\endgroup$
2
$\begingroup$

If the Discrete Log is easy, so is computationally DH.

According to:

Difiie-Hellman is as Strong as Discrete Log for Certain Primes

they [DH] conjectured that breaking their scheme would be as hard as taking discrete logarithms. This problem has remained open for the multiplicative group modulo a prime $P$ that they originally proposed. Here it is proven that both problems are (probabilisticly) polynomial—time equivalent if the totient of $P-1$ has only small prime factors with respect to $2 \log{P}$

$\endgroup$
  • $\begingroup$ Beware of asymptotic equivalences! For groups of realistic size, say $|G| \approx 2^{256}$, standard conjectures on the difficulty of the computational Diffie-Hellman problem assume $2^{128}$ difficulty, same as discrete log. Applying the reduction above requires $2^16$ calls to the DH oracle. As a result we only get out that DH is as hard as $2^102$, which is weaker than the commonly used conjecture, and a substantial gap from our best algorithms. So while the above paper suggests an asymptotic equivalence, the constant factors make it hard to apply in practice. $\endgroup$ – Watson Ladd Oct 13 '15 at 14:38
  • $\begingroup$ @WatsonLadd believe I cited correctly. $\endgroup$ – joro Oct 13 '15 at 15:04
  • $\begingroup$ You did, but the results are considerably weaker than what is commonly assumed true. So when someone gives an explicit reduction to CDH, the protocol won't be as secure if they were to use the above paper instead of the standard conjecture, and the difference is significant. $\endgroup$ – Watson Ladd Oct 13 '15 at 15:37
  • 1
    $\begingroup$ Note that joro's reference is about CDH, rather than DDH. $\;$ $\endgroup$ – user5810 Oct 13 '15 at 19:03
  • $\begingroup$ @RickyDemer Indeed, but I thought the OP asked about CDH, not DDH (DDH in some pairing based crypto is easy, while DL is considered hard). $\endgroup$ – joro Oct 14 '15 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy