# Understanding the groups used in bilinear Ate-pairing

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

\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}

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.

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

• This makes a lot of sense, thank you. Btw, I think there should be $[p]$ instead of $[1]$ in the second $Ker$.
– M.P
Apr 8 '20 at 16:48
• @M.P thanks, I've fixed it Apr 8 '20 at 17:23