2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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