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?

Improve this question
$\endgroup$
5
  • $\begingroup$ This might help What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman? $\endgroup$
    – kelalaka
    Commented Feb 18, 2021 at 8:10
  • 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
    Commented Feb 18, 2021 at 9:08
  • 1
    $\begingroup$ @YehudaLindell Uh, I read incorrectly, $\endgroup$
    – kelalaka
    Commented Feb 18, 2021 at 9:56
  • $\begingroup$ Thank you for your answers. But I couldn't find my answer. $\endgroup$
    – Mahdi Mahdavi
    Commented 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
    Commented Feb 19, 2021 at 20:43

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\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$
    – Mahdi Mahdavi
    Commented 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.