4
$\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!

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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."

$\endgroup$
3
  • $\begingroup$ One comment, though: the problem as posed is not exactly CDH as I understand it; isn't CDH the problem of, given $g$, $g^a$ and $g^b$, find $g^{ab}$ without knowing $a$ and $b$? Here we are given $g^a$, $g^b$, and $g^{ab}$, and we are trying to find $a$ or $b$; (it's not clear to me if we are also given $g$ or not). $\endgroup$
    – Arturo Magidin
    Commented Mar 22, 2011 at 19:36
  • $\begingroup$ @Arturo, you're right in your description of CDH and that the first question posed is different from it, but the asker also asks "That is can we use the solution of a CDH Problem to solve a DL?" and this is what I've attempted to answer. The first question asked sounds a lot like does the discrete log problem reduce to the pairing inversion (PI) problem (under some specific constraints). Note that since CDH <= PI and PI <= DL, the questions are similar in that if DL <= PI and PI <= CDH, then DL <= CDH, and I've tried to skip the PI problem that is presented ("<"= means poly-time reduction) $\endgroup$
    – Jan Gorzny
    Commented Mar 22, 2011 at 20:45
  • $\begingroup$ 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. $\endgroup$
    – Arturo Magidin
    Commented Mar 22, 2011 at 20:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .