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?

  • 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$ Feb 18, 2021 at 9:08
  • 1
    $\begingroup$ @YehudaLindell Uh, I read incorrectly, $\endgroup$
    – kelalaka
    Feb 18, 2021 at 9:56
  • $\begingroup$ Thank you for your answers. But I couldn't find my answer. $\endgroup$ Feb 19, 2021 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, 2021 at 20:43

1 Answer 1


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.

  • $\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$ Feb 20, 2021 at 3:09

Your Answer

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

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