3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I'm assuming DH is diffie helman ? is there a link to a description of the problem ? is this well known ? $\endgroup$ – Suresh Venkat Mar 11 '14 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 Mar 12 '14 at 4:21
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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 Mar 27 '14 at 16:17

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.