Score:1

Isomorphic mapping of BLS12-381 G2 points to G1

ca flag

I'm attempting to reproduce ring signatures as described in Section 5 of https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf but applied to the BLS12-381 system.

enter image description here One of the assumptions in their construction is that an isomorphism ψ: G2 → G1 exists, with ψ(g2) = g1

There's a hint that we may be able to use a trace map as this isomorphism:

enter image description here

Now I've found the definition of trace maps in Pairings for Beginners (search for trace map)

enter image description here

But all attempts I've made of implementing this trace map have been unsuccessful, none of the points that I mapped from the BLS12-381 G2 group were landing on the G1 curve.

I think I'm missing something. Should I expect the outputs of this trace map to produce points in G1?

Maybe I'm not approaching this correctly?

Daniel S avatar
ru flag
One gotcha is that the summation in the trace formula should be interpreted with the elliptic curve group operation. Are you finding that the coordinates of the trace do not lie in $\mathbb F_q$ or is it that they do not satisfy the curve equation?
Score:2
kr flag

The setting described in that paper is an instance of a so-called “Type-II pairing” with an efficient isomorphism $G_2\to G_1$. Most efficient pairing constructions are “Type-III”, where such an isomorphism is believed not to exist. So if you take a normal implementation of the BLS12 bilinear group, this won't work: ignoring twists, you can indeed compute the trace map as mentioned, but the $G_2$ subgroup is specifically chosen to map to zero, so it won't be an isomorphism.

To be a bit more precise, the construction of bilinear pairings looks like this. We start with an elliptic curve $E/\mathbb{F}_q$ such that the $p$-torsion subgroup $E[p](\mathbb{F}_q)$ (points of order dividing $p$ with coordinates in $\mathbb{F}_q$) is cyclic of order $p$, and such that moreover, over some small degree extension $\mathbb{F}_{q^d}$, $E$ has full $p$-torsion (i.e., $E[p](\mathbb{F}_{q^d})$ is isomorphic to $(\mathbb{Z}/p\mathbb{Z})^2$: there are $p^2$ points with coordinates in $\mathbb{F}_{q^d}$ and order dividing $p$). We can then choose $E[p](\mathbb{F}_{q^d})$ as $G_1$, and any of the other $p$ subgroups of order $p$ of $E[p](\mathbb{F}_{q^d})$ as $G_2$.

Now, as described in the paper, the trace map is a homomorphism of $E[p](\mathbb{F}_{q^d})$ onto $G_1$, so the usual choice of $G_2$ is to take the kernel of this map. This allows all sorts of optimizations of the construction, makes it possible to hash to $G_2$ and so on and so forth, but it is precisely incompatible with the setting required in that paper. What you would do for that paper is choose one of the remaining $p-1$ choices for $G_2$ (or more likely: modify the construction in order to avoid the less efficient Type-II setting; there exist automatic conversion tools that take a primitive defined in one setting and formally construct a corresponding primitive in another setting, so this should be possible here, although the security argument might need to be adapted normally).

David Rusu avatar
ca flag
This is very helpful, Merci beaucoup!
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.