Let $G$ be a group, $g ∈_R G, x ∈_R Z_q$, and $e: G \times G \rightarrow G_T$ be a bilinear paring.

Then, given $g, g^x$, is it still hard to compute $g^{x^2}$?

1. In other words is Square Diffie-Hellman hard in Bilinear Groups?

I am trying to look for references that have used this problem or a reduction which proves this is hard.

[I am aware of a variant of this called the Flexible Square Diffie-Hellman [Laguillaumie et al], which asks to compute $(h,h^x,h^{x^2})$ given $g^x$.]

2. What about the decisional version of the same problem?

  • 2
    $\begingroup$ I'm assuming DH is diffie helman ? is there a link to a description of the problem ? is this well known ? $\endgroup$ Commented Mar 11, 2014 at 17:34
  • $\begingroup$ Yes, DH is Diffie Hellman. And no, I don't think the problem is well known (at least in the bilinear setting). Otherwise, traditional square DH is quite popular and is known to be as hard as CDH. $\endgroup$
    – Subhayan
    Commented Mar 12, 2014 at 4:21

1 Answer 1


This assumption has been used in cryptographic constructions. Both the computational and decisions are generally believed hard by the provable security community, but I doubt a reduction to, e.g., DH will be found. See http://homepage.ruhr-uni-bochum.de/Eike.Kiltz/papers/dh_full.pdf for discussion and references.

  • $\begingroup$ So, from the paper, can I infer, given $g,h∈G,\ g^a$, it is hard to compute $e(g,h)^{a^2}$ ? $\endgroup$
    – Subhayan
    Commented Mar 27, 2014 at 16:17

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.