The standard DDH assumption states that given $(g,g^a,g^b,g^c)$, it is hard to determine whether $c$ is $ab$ or not.

A variant of DDH assumption is: given $(g,g^a,g^b,g^c, g^{ab} ,g^{bc},g^{ac})$, it is hard to whether the last three terms are random or not.

Is the variant still secure? If then, how to prove this?

  • $\begingroup$ Let Adv be the advantage of a variant, and Adv_DDH be the that of DDH. Then, is it true that $Adv \le c* Adv_DDH$ for some constant $c$? $\endgroup$ Feb 12 at 14:13
  • $\begingroup$ What is the negative distribution (that is, the distribution the Oracle is expected to say 'false' to)? Is it $(g, g^a, g^b, g^c, g^d, g^e, g^f)$? Or, is it $(g, g^a, g^b, g^c, g^{ab}, g^{bc}, g^d)$ (for some ordering of the last three terms)? $\endgroup$
    – poncho
    Feb 12 at 14:24
  • $\begingroup$ @poncho Thanks you for comments. $(g,g^a,g^b,g^c,g^d,g^e,g^f)$ is right. That is, the variant assumption is that any PPT adversary is hard to distinguish between $(g,g^a,g^b,g^c,g^d,g^e,g^f)$ and $(g,g^a,g^b,g^c,g^{ab},g^{bc},g^{ca})$. I think the advantage could be bound by $c\cdot Adv_{DDH}$ for some $c$ since given the challenging query $(g,g^a,g^b,g^c,g^d,g^e,g^f)$, if the adversary of the variant can access to an oracle for solving DDH, he can try all possible 3-tuples. Is it right? $\endgroup$ Feb 12 at 14:30
  • 1
    $\begingroup$ We had a similar question crypto.stackexchange.com/q/98535/18298 $\endgroup$
    – kelalaka
    Feb 12 at 15:50
  • $\begingroup$ @kelalaka Thank you $\endgroup$ Feb 13 at 2:20


Your Answer

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