Understanding the groups used in bilinear Ate-pairing

Question

The bilinear ate pairing $e:G_1\times G_2 \rightarrow G_T$ is defined over the following groups:

\begin{equation} \begin{aligned} & G_1 = E(\mathbb{F}_p)[r] \cap Ker(\pi_p-[1]), \\ & G_2 = E(\mathbb{F}_{p^k})[r] \cap Ker(\pi_p-[p]), \\ & G_T = \mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r, \end{aligned} \end{equation}

where $E(\mathbb{F}_{p^k})[r]$ is $r$-torsion points of elliptic curve $E(\mathbb{F}_{p^k})$, $\pi_p$ is the Frobenius endomorphism and $[n]$ is the scalar multiplication of a rational point $n$.

I'm having trouble understanding the structures of the groups. Especially I'm confused with this mapping $\pi_p-[n]$ and the notation $\mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r$ as whole. Further explanation, why the groups are like this and other discussion is also welcome. Thanks in advance.

Source: Implementing Cryptographic Pairings over Barreto-Naehrig Curves.

Answer 1

$E(\mathbb{F}_{p^k})[r]$: all elements $P$ of $E(\mathbb{F}_{p^k})$ such that $rP = 0$. In other words, all points whose order divide $r$. In protocols $r$ is usually prime, so that means all points with order $r$ and the point at infinity.

$\pi_p$: the Frobenius endomorphism. This is a function that takes an elliptic curve point such that $\pi_p((x, y)) = (x^p, y^p)$.

$[1]$: the identity function, i.e. $[1](P) = P$

$\pi_p - [1]$: the function $(\pi_p - [1])(P) = \pi_p(P) - [1]P$

$Ker(\pi_p - [1])$: the kernel of the given function. The kernel of a function is composed of all elements that map to the identity element. In our cases, all points $P$ such that $\pi_p(P) - [1]P = 0$, i.e., $\pi_p(P) = P$. In non-extension finite fields (i.e. $k = 1$) it is true that $x^p = x$ and therefore $\pi_p(P) = P$ for every point with coordinates in a non-extension field. Therefore $Ker(\pi_p - [1]) = E(\mathbb{F}_{p})$ and that was a huge roundabout way to write that $G_1$ is the same as $E(\mathbb{F}_{p})[r]$.

$Ker(\pi_p - [p])$: following the same reasoning, in this case, these are all the points $P$ such that $\pi_p(P) = pP$, i.e. the Frobenius mapping is a much faster way to compute $pP$, which is a much more interesting mapping. Therefore $G_2$ are all the $r$-torsion points in $E(\mathbb{F}_{p^k})$ where that equality is true.

$\mathbb{F}_{p^k}^*$: the multiplicative subgroup of the finite field $\mathbb{F}_{p^k}$ (i.e. all non-zero elements under the multiplication operation).

$(\mathbb{F}_{p^k}^*)^r$: the multiplicative subgroup where all elements are raised to the $r$-th power.

$\mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r$: this is the confusing part. This is a quotient group, and its elements are cosets (sets of field elements). Elements $x,y$ are in the same coset if $x/y = h^r$ for some element $h$. There will be $r$ such cosets, each with $(q^k-1)/r$ elements. However, since it is difficult to work with cosets in cryptographic protocols, in the end they select a "canonical" element by raising the element of the coset (which is the intermediate result of the pairing computation) by $(q^k-1)/r$, the so-called "final exponentiation". This implies that the set of canonical coset elements are the $r$-th roots of unity, i.e. all elements $x$ such that $x^r = 1$ (because $x$ was already the result of exponentiation by $(q^k-1)/r$, if we raise that by $r$, we are computing the full exponentiation by $q^k-1$ which is the order of the multiplicative subgroup and we get back to $1$).