# Hard Problems in Pairings

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?

## 1 Answer

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.