# How to determine if a bilinear map satisfies XDLIN?

Let $$\{(q, G_1, G_2, G_T, e: G_1 \times G_2\to G_T)_s\}$$ be a family of bilinear groups parameterized by the security parameter $$s$$. We use $$g_1$$ (resp. $$g_2$$) to denote the generator of $$G_1$$ (resp. $$G_2$$).

The XDLIN problem is to guess bit $$B$$ ($$B = 0$$ or 1), given

$$P_B:= \{g_1^a, g_1^b, g_1^{ac}, g_1^{bd}, g_2^a, g_2^b, g_2^{ac}, g_2^{bd}, Y_B\},$$

where $$Y_0 = g_x^{c+d}$$, $$Y_1 = g_x^r$$ ($$x = 1$$ or 2), and $$a, b, c, d, r$$ are sampled uniformly, independently at random from $$\{0, 1, ..., q - 1\}$$.

If the advantage for the XDLIN problem is negligible in $$s$$ for every PPT adversary, then we say that the XDLIN assumption holds.

The bilinear map can be constructed using Tate and Ate pairings of elliptic curves. But it is unclear to me how to determine if a family of bilinear groups satisfies the XDLIN. Is it possible that the XDLIN assumption holds for bilinear maps generated by using Barreto-Naehrig Curves? Or more generally, as long as the discrete log problem is hard for $$G_1$$ and $$G_2$$, then the XDLIN assumption holds?

If the discrete logarithm problem is easy (requires work less than that permitted by $$s$$) in either $$G_1$$ or $$G_2$$ then the XDLIN assumption does not hold. However, we do not know if the converse is true. There may be constructions where the discrete logarithm is hard, but the XDLIN problem is solvable. This is why we introduce XDLIN as a distinct assumption from discrete logarithm, computational Diffie-Hellman and decisional Diffie-Hellman.