1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Daniel S
    Oct 29 at 6:58
2
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ This is very helpful, Merci beaucoup! $\endgroup$
    – David Rusu
    Oct 29 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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