1
$\begingroup$

I'm curious about the relation between the Discrete Logarithm and Decisional Diffie-Hellman. Is it safe to have an assumption like the following to link the two?

Given uniformly and independently chosen g^x and g^y, if there is an efficient algorithm that can distinguish g^(xy) and random g^r with non-negligible probability, then there is an extractor that can extract x or y with non-negligible probability?

This looks like a Knowledge of Exponent assumption, however, I want it to tackle the decisional problem. Also it is known that some elliptic curve groups could use pairing to break DDH, in this case, we'll restrict the discussion to groups such as the group of Quadratic Residue over Blum integers.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I think that making this link is not common at all.

A good reason is that for example bilinear group with symmetric pairing (Type 1) can be considered as secure for the discrete-log assumption but it will be never the case for the DDH assumption.

If you receive $(g,x,y,z)$, you can easily check if $e(g,z)=e(x,y)$, and this equality is enough to decide if it is a Diffie-Hellman tuple or not.

To see a more theoretical reason, you can look the Gap-DH assumption (in this problem the adversary has to solve a CDH instance with a DDH oracle) : Thus it has been shown that if for any algebraic adversary, if DLog holds, then Gap-DH is also a hard problem (thus if you replace a CDH instance by a DLog instance it becomes still harder).

You can look this phd page 136 for more details

https://www.iacr.org/phds/index.php?p=detail&entry=1476

And because considering algebraic adversary seemed to me equivalent to the Knowledge of Exponent assumption, thus it would be really weird to make a such link (as far as I understood, it will imply that Dlog is easy, but I'm not completely sure about that).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the insights! $\endgroup$
    – Sean
    Jun 29, 2021 at 22:24
  • $\begingroup$ Now, what if we restrict the discussion to those groups where the DDH problem is believed to be difficult (e.g., those non-Gap_DH groups)? $\endgroup$
    – Sean
    Jun 29, 2021 at 22:25
  • $\begingroup$ I do not understand what do you mean. But do not hesitate to ask a new question with another post, it would be clearer. $\endgroup$
    – Ievgeni
    Jun 30, 2021 at 6:57
  • $\begingroup$ I posted another question as below. This explains why I need to link it to Knowledge of Exponent assumption. $\endgroup$
    – Sean
    Jun 30, 2021 at 13:01
  • $\begingroup$ The link is below: crypto.stackexchange.com/questions/91834/… $\endgroup$
    – Sean
    Jun 30, 2021 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.