Pairing groups

Any full r-torsion group contains $r + 1$ cyclic subgroups, two of which are of particular interest in pairing-based elliptic curve cryptography. To characterize these groups, we need to consider the so-called Frobenius endomorphism of an elliptic curve $E(F)$ over some finite field $F$ of characteristic $p$:

$$\pi: E(F) \to E(F): \begin{cases} (x, y) \to (x^p, y^p) \\ O \to O \end{cases}.$$

It can be shown that $π$ maps curve points to curve points. The first thing to note is that, in case $F$ is a prime field, the Frobenius endomorphism acts as the identity map, since $(x^p, y^p) = (x, y)$ on prime fields due to Fermat’s little theorem. This means that the Frobenius map is more interesting on elliptic curves over prime field extensions.

With the Frobenius map at hand, we can characterize two important subgroups of the full $r$-torsion group $E[r]$ of an elliptic curve. The first subgroup is the group of elements from the full $r$-torsion group, on which the Frobenius map acts trivially. Since in pairing-based cryptography, this group is usually written as $G_1$, assuming that the prime factor $r$ in the definition is implicitly given, we define $G_1$ as follows:

$$G_1[r] = \{(x, y) ∈ E[r] | π(x, y) = (x, y) \}.$$

It can be shown that $G_1$ is precisely the $r$-torsion group $E(F_p)[r]$ of the unextended elliptic curve defined over the prime field.

There is another subgroup of the full $r$-torsion group that can be characterized by the Frobenius map and in the context of pairing-based cryptography, this subgroup is often called $G_2$. This group is defined as follows:

$$G_2[r] = \{(x, y) ∈ E[r] | π(x, y) = [p](x, y) \}.$$

Notation: If $E(F)$ is an elliptic curve and $r$ is the largest prime factor of the curves order, we call $G_1[r]$ and $G_2[r]$ pairing groups. If the prime factor $r$ is clear from the context, we sometimes simply write $G_1$ and $G_2$ to mean $G_1[r]$ and $G_2[r]$, respectively.

It should be noted that other definitions of $G_2$ exists in the literature, too. However, in the context of pairing-based cryptography, this is a common choice as it is particularly useful because we can define efficient hash functions that map into $G_2$, which is not possible for all subgroups of the full r-torsion.