2
$\begingroup$

I want to know whether the following problem is considered as a hard problem in complexity theory or not?

Given $g,g^a,g^b \in G_1$ (for unknown $a,b\in \mathbb{Z}_p^{\ast}$), compute $e(g,g)^{ab^2}\in G_2$.

If yes, could you please help me to know the name of this problem in the literature?

$\endgroup$
2
$\begingroup$

There is a generalisation of the Diffie-Hellman problem to multi-linear groups known as the multi-linear Diffie-Hellman problem (MDHP, see this paper for example). Specifically, for a group $G_1$ endowed with an $n$-multi-linear map $e$ to a group $G_2$ the MDHP is: given $g, g^{a_1}, g^{a_2},\ldots, g^{a_{n+1}}\in G_1$ compute $e(g,g,\ldots,g)^{a_1a_2\cdots a_{n+1}}\in G_2$.

Your problem is clearly no harder than the MDHP for $n=2$ (take $a_1=a$, $a_2=b$, $a_3=b$), and if we can take square roots in either $G_1$ or $G_2$ then a solution to your problem solves MDHP with $n=2$.

To turn your problem into a 2DHP solver in the case where we can take square roots in $G_1$, $a=a_1$ and let $g^{b_1}=g^{a_2}g^{a_3/2}$ so that $b_1=a_2+a_3/2$ and $g^{b_2}=g^{a_2/2}/g^{a_3/2}$ so that $b_2=a_2/2-a_3/2$, then $$e(g,g)^{ab_1^2}/e(g,g)^{ab_2^2}=e(g,g)^{a_1a_2a_3}.$$

Likewise if we can take square roots in $G_2$ let $b_1=a_2+a_3$ and $b_2=a_2-a_3$, then $$\left(e(g,g)^{ab_1^2}/e(g,g)^{ab_2^2}\right)^{1/4}=e(g,g)^{a_1a_2a_3}.$$

Note that square roots are easy to take in cyclic groups of known odd order, which covers a great deal of cryptographic applications.

$\endgroup$

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.