4
$\begingroup$

Is this problem still hard?

Given $$(g,g^a,g^b,c)$$ decide if $c=a\cdot b$?

If there is an adversary that solves the standard Decisional Diffie-Hellman Problem then it can solve my new problem. But I can't understand that my new problem still hard or not.

Did anyone see this problem or similar to my problem? Can anyone help me?

$\endgroup$
5
  • 2
    $\begingroup$ @kelaka This doesn't answer the question. Indeed, as the question states - it is clear that if DDH is easy then so is this. However, this is not DL or CDH or DDH since the actual value $c=a\cdot b$ is given, and not $g^c$. $\endgroup$ – Yehuda Lindell Feb 18 at 9:08
  • 1
    $\begingroup$ @YehudaLindell Uh, I read incorrectly, $\endgroup$ – kelalaka Feb 18 at 9:56
  • $\begingroup$ Thank you for your answers. But I couldn't find my answer. $\endgroup$ – mehdi mahdavi oliaiy Feb 19 at 12:47
  • 3
    $\begingroup$ As an aside, I would note that the similar problem "given $(g, g^a, g^b, c)$ is $c = a / b$" turns out to be easy... $\endgroup$ – poncho Feb 19 at 20:43
6
$\begingroup$

Yes it is. It can be formally reduced to the hardness of the decisional square Diffie-Hellman assumption, which states that distinguishing $(g,g^a,g^{a^2})$ from random is hard (this is a well established assumption).

It follows in a relatively simple way from the answer I wrote here to a related question. I can let you work out the details in case you want to play a bit with these reductions. In case you cannot figure out the formal reduction, just ask in the comment and I will elaborate.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer. I think that my problem reduced to the decisional inverse Diffie-Hellman assumption, which states that distinguishing $(g,g^a,g^{a^{-1}})$ from random. $\endgroup$ – mehdi mahdavi oliaiy Feb 20 at 3:09

Your Answer

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

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