Choosing asymmetric pairing for Elliptic Curves

Question

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

Answer 1

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.

Answer 2

There are slim chances to "just choose proper $G_2$". There are families of specific curves such that $G_2$ will have proper number of points. Supersingular curves with $(p+1)$ points for the curve over the base prime field could be an easy example. MNT and BN curves would be better examples. "Specific instantiation" part means a few more papers to read.

Answer 3

Let's start from the beginning. We have symmetric encryption, an AES128 for example is said to have a security level $128$ because we need $2^{128}$ operations to recover the key (brute force). However, symmetric encryption has the vulnerability of symmetric key storage. As a solution we have asymmetric encryption; the first schemes were DH, RSA and ElGamal. The latter relies on the discrete logarithm problem (DLP) $-$ given $g$ and $g^a$ in a finite field $\mathbb{F}_p$ it is conjectured difficult to recover $a$.

The fastest known algorithm to compute discrete logs (up to Kim and Barbelescu paper) is the General Number Field Sieve (GNFS) which has a sub-exponential complexity. This means that to have an Elgamal with a 128 security level, we need a prime $p$ of 3072 bits. Elliptic curves were introduced to transfer the DLP to a generic group model in the sense of Victor Shoup, resulting in the Elliptic Curve DLP (ECDLP). The advantage is the absence of sub-exponential algorithms such as GNFS to find discrete logs in this group. Consequently, we can use an elliptic curve group that is smaller in size while maintaining the same level of security. For instance, one we need a prime $p$ of $256$ bits to have a 128 security level because the fastest known algorithm to break ECDLP is Pollard's $\rho$ with a complexity $\approx \mathcal{O}(\sqrt{p})$. Truth to tell, the complexity is $\mathcal{O}(\sqrt{r})$ where $r$ is the subgroup order.

To avoid attacks using the Chinese Remainder Theorem (CRT) we often use elliptic curves of prime order, so $r$ is equal to the group order according to Lagrange's theorem and since the gap between $p$ and the group order is at most $2\sqrt{p}$ according to Hasse's theorem, we say that the Pollard's $\rho$ complexity is $\approx \mathcal{O}(\sqrt{p})$.
Now, the question is: If we can transform the DLP to the ECDLP, can't we transform the ECDLP to the DLP? The answer is Yes using non-degenerate bi-linear maps called pairings. Given two subgroups $G_1$ and $G_2$ of prime order $r$, a pairing $e$ maps bi-linearly $G_1 \times G_2$ to $\mathbb{F}_{p^k}$ where $k$ is an integer called the embedding degree. For instance, given the points $P$ and $Q=a.P$, we have $e(P,Q)=e(P,a.P)=e(P,P)^a \in \mathbb{F}_{p^k}$. Since $P$, $Q$ are public and since $e$ is non-degenerate ($e(P,P) \ne 1$), we can easily compute the integers $X=e(P,Q)\in \mathbb{F}_{p^k}$ and $Y=e(P,P)\in \mathbb{F}_{p^k}$, yielding $X=Y^a$. This way, we have transformed the ECDLP to the DLP in $\mathbb{F}_{p^k}$.

Now to avoid this attack, we would want the embedding degree $k$ to be big enough. Indeed, standardized elliptic curves such as secp256k1 have an embedding degree $k \approx p$ ($256$ bits for secp256k1) which makes the attack uninteresting. This was the "destructive" use of pairings but they can be used in a "constructive" way to build elegant cryptographic solutions such as identity-based encryption, one-round three-party Diffie-Hellman or short BLS signatures. To do this, we would want the embedding degree $k$ to be small enough so that computations in $\mathbb{F}_{p^k}$ would be feasible but at the same time $k$ must be big enough to avoid the "destructive" use of pairings. It turns out that the optimal choice of $k$ is $12$ because the complexities ratio of Pollard's $\rho$ (ECDLP breaker) and GNFS (DLP breaker) is $12$. The class of elliptic curves that satisfy this dilemma is called "pairing-friendly elliptic curves".

Constructing a pairing-friendly curve is not a easy topic to deal with. You can use Barreto-Naehrig curve BN(2,256) which have an embedding degree $k=12$ and a security level around 128. But since Kim and Barbelescu paper, the BN(2,256) was reduced to around 110 so you can use BLS12-381 otherwise. Now going back to pairings, there are three types: symmetric when $G_1=G_2$, weak asymmetric when $G_1 \ne G_2$ but there is an efficiently computable homomorphism $\phi : G_2 \rightarrow G_1$, and strong asymmetric when $G_1 \ne G_2$ and there are no efficiently computable homomorphisms between $G_1$ and $G_2$. It is common to define pairing-friendly curve such as Barreto-Naehrig on sextic twists to implement efficient type-3 pairings (https://eprint.iacr.org/2012/232.pdf).