0
$\begingroup$

In Number Theory, Given the Diffie Hellman tuple (ga,gb,gab), Will the given info be helpful in finding the discrete log of g ,i.e a or b?

Edit: That is can we use the solution of a Computational Diffie Hellman Problem to solve a Discrete Log. It is known that the converse is true!

1 Answers 1

3

A paper (note: SpringerLink, may require subscription) called "Separating Decision Diffie–Hellman from Computational Diffie–Hellman in Cryptographic Groups∗" published in '03 in the Journal of Cryptology has the following quote,

"In 1994 Maurer used a variation of the elliptic curve factoring method to give strong evidence that CDH and DL are probably equivalent (see [9]). This approach was formalized by Maurer and Wolf in [10] and finally appeared as a journal version in [11]." (where CDH = "Computational Diffie-Hellman" and DL = "Discrete Log")

Where the relevant citations are included below.

The paper goes on to say "Our goal in this paper is to merge the two approaches and to construct a family of groups where CDH and DL are equivalent and presumably hard". Assuming "equivalent" here means CD reduces to DL and DL reduces to CDH, this seem relevant.

So while this isn't a complete answer, the answer might be that at least occasionally we can use a CDH solution to solve a DLog. (Note: I haven't read this paper (yet) so I don't know that they actually met their goal, so this too might be wrong! If someone familiar can confirm whether or not they did, that would be great--I don't have the time or battery life right now to do so.)

I suspect [11] might shed more light on the issue, if you can find it (I haven't looked), and there may be more recent results.

"[9] U. Maurer. Towards the equivalence of breaking the Diffie–Hellman protocol and computing discrete logarithms. In Advances in Cryptology -CRYPTO’94, volume 839 of Lecture Notes in Computer Science, pages 271–281. Springer-Verlag, Berlin, 1994.

[10] U. Maurer and S. Wolf. Diffie–Hellman oracles. In N. Koblitz, editor, Advances in Cryptology - Crypto ’96, Volume 1109 of Lecture Notes in Computer Science, pages 268–282. Springer-Verlag, Berlin, 1996.

[11] U. Maurer and S. Wolf. The relationship between breaking the Diffie–Hellman protocol and computing discrete logarithms. SIAM Journal on Computing, 28(5):1689–1721, 1999."

  • 0
    Good points. Thanks for calling my attention to them. I do note that the OP says "That is...", which suggests$a$belief that the first question is the same as the second. It might be worth noting that the two are not quite equivalent.2011-03-22