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?


1 Answer 1


As with all hardness assumptions, it is unclear to everyone how to determine if the assumption holds for any given construction. There may be cases where we can demonstrate that the assumption does not hold, but otherwise it is an assumption rather than a determinable property. At present, we cannot show that the assumption does not hold for Barreto-Naehrig curves with their security estimates as laid out by Barbulescu et al. and so we believe that it is reasonable to create constructions based on the XDLIN assumption using these groups.

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.

  • $\begingroup$ Thank you very much! In your opinion, what type of curves would be best suited for implementing schemes based on pairings in real life? $\endgroup$
    – heller
    Commented Apr 11, 2023 at 4:22
  • 1
    $\begingroup$ @heller It depends on your requirements. BN and BLS curves are well-supported, with a choice of implementations. For efficiency and security, I like the Brezing-Weng prime extension construction, but this might involve writing your own library. For simplicity of implementation, supersingular curves over large primes are the easiest, but not very efficient. $\endgroup$
    – Daniel S
    Commented Apr 11, 2023 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.