How to find second subgroup for ECC Pairing?

Pretty new to ECC Pairings. I am trying to understand KZG Commitments from multiple sources. I found this blog beginner friendly and easier to understand. However, I'm stuck at ECC Pairings and having difficulty in order to completely understand it.

The blog mentioned:

• Input: 2 points ($P$ and $Q$) on 2 subgroups of the same curve ($\mathbb{G}_1$ and $\mathbb{G}_2$).
  • $\mathbb{G}_1$ is a subgroup of points for the elliptic curve, which in the form $y^2 = x^3 + b$, and both $x$ and $y$ are simple integers ($x,y ∈ F_p$ )
  • $\mathbb{G}_2$ is another subgroup of points for the same elliptic curve above (points satisfy the same equation as $\mathbb{G}_1$), but both $x$ and $y$ are elements of supercharged complex numbers ($x,y ∈ F_{p^{12}}$ ). $x$ and $y$ are in the format of $w^{12} - 18 * w^6 + 82 = 0$

I didn't understand how we can find generator for the second group $\mathbb{G}_2$ and why we need an extension field of $F_{p^{12}}$. Can you please help me understand with a simple example?

The generator for $G_1$ is point $P$ on Elliptic Curve $E(F_p)$. Assume the order of $P$ is $m$.

You have to find the smallest positive integer $k$ such that

$p^k \equiv 1 \bmod m$

$k$ is called as the embedding degree of the curve $E(F_p)$ with respect to $m$.

$k$ in your example is $12$

The point $P \in E(F_p)$ which satisfies $mP=\mathcal O$ is called a $m$-torsion point. The subgroup of all $m$-torsion points in $E(F_p)$ is called the $m$-torsion subgroup of $F_p$ & is denoted by $E(F_p)[m]=\{P\in E:mP=\mathcal O\}$. $G_1$ is this subgroup & $P$ is the generator.

Now since the extension field $F_{p^k}$ is bigger than $F_p$, $E(F_{p^k})$ may contain more $m$-torsion points than $E(F_p)$ (Note - $k$ is the embedding degree wrt $m$).

The biggest $m$-torsion group is found in the extension field $F_{p^k}$ i.e. going to a bigger extension field than $F_{p^k}$ doesn’t add any more m-torsion points. $E(F_{p^k})[m]$ is called the full $m$-torsion group.

• Next you have to compute the order of the elliptic curve of $F_{p^k}$. Let it be $n$.

  i.e. $n = \#E(F_{p^k})$

  Since the $m$-Torsion group of $E(F_p)$ is a subgroup of $E(F_{p^k})$, $m$ divides $n$ as per Lagrange’s Theorem.

• Choose a random point $R \in E(F_{p^k})$ such that $R \notin E(F_p)$

• Calculate $Q=(\frac{n}{m})R$. If $Q= \mathcal O$, then go back to previous step & chose another random point $R$. If it’s not $\mathcal O$, then it’s a point of order $m$ like shown below

  $Q = (\frac {n}{m}) R$

  So $mQ = nR$

  Let $r$ be the order of $R$. By Lagrange’s Theorem, $r$ divides the order of $E(F_{p^k})$. i.e. $r$ divides $n$. So $n$ can be written as $n=dr$ for some $d$.

  So $mQ= drR$.

  Since $rR = \mathcal O$, $drR = \mathcal O$

  So $mQ = \mathcal O$.

  So the order of $Q$ is $m$. Let's call this subgroup of order $m$ as $G_2$. $Q$ is the generator for the subgroup $G_2$

The above is how you find the right extension field, the 2nd subgroup, the generator for the 2nd subgroup in a Weil Pairing.

You can read about Pairings, Weil Pairings, Embedding Degree etc from any Elliptic Curve text which covers pairings

• Mathematical Cryptography by Silverman et al

• Guide to Elliptic Curve Cryptography by Menezes, Vanstone et al

• Elliptic Curves by Lawrence Washington