Choosing asymmetric pairing for Elliptic Curves I'm trying to implement a Provable Data Posession protocol using elliptic curves, but am stuck at the $\text{KeyGen}$ phase of choosing a subgroup $G_2$. Here's an excerpt of it.


  On input $\mathcal{K}$, choose an elliptic curve $E(\mathbb{F}_q)$ with a subgroup of large prime order $p$ generated by $P\in E(\mathbb{F}_q)[p]$, such that the bitlength of $p$ is $\mathcal{K}$. Choose an asymmetric pairing $e: E(\mathbb{F}_q)[p] \times G_2 \rightarrow \mathbb{F}_{q^k}^*[p]$ with $G_2$ being a p-order elliptic curve subgroup over (an extension of) the field $\mathbb{F}_q$ with generator $P'$, where the choice of $G_2$ depends on the specific instantiation of the pairing.


If I've understood it right, I can choose some curve, e.g. p256, secp256k1, or something else. But then I also need a subgroup $G_2$.

How do I choose a $G_2$ that satisfies the asymmetric pairing that is stated above?



Link to paper (page 7): https://eprint.iacr.org/2013/392.pdf
Not all elliptic curves are suitable for use with pairings - you need to choose a pairing-friendly curve. There are several families of pairing-friendly curves; one of these is the set of Barreto-Naehrig curves. They are a good place to start.

For pairings that require that $G_1$ be distinct from $G_2$ (type 3 pairings, including the optimal Ate pairing), $G_2$ can be computed as the trace zero subgroup of the $r$-torsion; that is, it is the set of points which lie in the kernel of the trace map.

If $E$ is a Barreto-Naehrig curve, we know that the $r$-torsion embeds in the degree-12 extension $E(\mathbb{F}_{q^{12}})$. We also know that there is a related curve $E'$ (often called the twisted curve) over the degree-two extension $E(\mathbb{F}_{q^2})$ for which an efficiently computable group isomorphism $\psi : E'(\mathbb{F}_{q^2}) \to E(\mathbb{F}_{q^{12}})$ exists.

In our work, we generated elements of $G_2$ by first choosing arbitrary points on $E'(\mathbb{F}_{q^2})$, then converting them to $r$th roots. This is done using the fact that the order of $E'$ is $r * (2q - r)$, so if we multiply a point $p$ by $2q - r$, we get a point of order $r$. Once we have the $r$th root, we map it into the trace zero subgroup $G_2$ using the anti-trace map, defined as

$aTr(P) = 12 \cdot P - Tr(P)$

where the trace of a point $P = (x, y)$ on $E'$ is defined as

$Tr(P) = \sum_{i=0}^{11}(x^{q^i}, y^{q^i})$

where addition is elliptic curve point addition on $E'$.

I know this is pretty hand-wavy. There is a lot more detailed description in the online book "Pairings for Beginners" by Craig Costello.