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, 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
    Mar 12, 2014 at 4:21

1 Answer 1

Reset to default
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, 2014 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.