3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.