Score:2

How to determine if a bilinear map satisfies XDLIN?

tm flag

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?

Score:1
ru flag

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.

heller avatar
tm flag
Thank you very much! In your opinion, what type of curves would be best suited for implementing schemes based on pairings in real life?
Daniel S avatar
ru flag
@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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.