On subgroup checks for BLS12

Let

$E$ be an elliptic curve from the BLS12 family. We denote by

$r$ its prime subgroup order. Let

$P(x,y)\in E$ a point of order

$r$. The goal is to verify efficiently that

$r\cdot P=\mathrm{\infty }$.

Notations

• $E$ is an elliptic curve defined over a finite field
  ${\mathbb{F}}_p$ with the short Weierstrass equation
  $y^2=x^3+ax+b$
• $r$ is a prime-order subgroup of
  $E({\mathbb{F}}_p)$
• $k$ is the embedding degree, i.e. the smallest integer s.t.
  $r\mid p^k-1$
• A pairing is a map
  $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\mapsto {\mathbb{G}}_T$, where
  ${\mathbb{G}}_1\subset E[r]({\mathbb{F}}_p)$,
  ${\mathbb{G}}_2\subset E[r]({\mathbb{F}}_{p^k})$ and
  ${\mathbb{G}}_T$ the group of
  $r$-th roots of unity in
  ${\mathbb{F}}_p$.

BLS12

BLS12 is a complete family of pairing-friendly elliptic curves with an embedding degree

$k=12$ (Construction 6.6 in FST06, case

$k\equiv 0\mathrm{mod}6$). It is defined over a finite field

${\mathbb{F}}_{\mathbb{p}}$ of prime characteristic

$p$ by the equation

$y^2=x^3+b$. It has Complex Multiplication by discriminant

$D=-3$ and parameters defined by the following polynomials:

Parameter	Polynomial
field size $p(x)$	$(x-1{)}^2/3\cdot r(x)+x$
subgroup order $r(x)$	$x^4-x^2+1$
Frobenius trace $t(x)$	$x+1$

$\to$ These polynomials are evaluated at some seed

$z$ to derive a specific curve with the desired security and efficiency.

Endomorphisms

BLS12 curves have CM discriminant

$D=-3$, so there is an efficient endomorphism

$\varphi :(x,y)\mapsto (x\cdot \omega ,y)$ with

$\omega \in {\mathbb{F}}_p$ a primitive cube root of unity (i.e.

${\omega }^2+\omega +1\equiv 0\mathrm{mod}p$). The eigenvalue of this endomorphism is

$\lambda =z^2-1$ which a cube root of unity in

${\mathbb{F}}_r$.

BLS12 has Complex Multiplication by

$\frac{-1+\sqrt{-3}}{2}$. There is an endomorphism

$\varphi$ satisfying

${\varphi }^2+\varphi +1$ with eigenvalue

$\lambda =\frac{-1+\sqrt{-3}}{2}\mathrm{mod}r$. Given BLS12 polynomials, one finds

$\lambda (x)=x^2-1$.

Given a twist of order

$d$,

${\mathbb{G}}_2\subset E[r]({\mathbb{F}}_{p^k})$ is isomorphic to

$E^{\prime }[r]({\mathbb{F}}_{p^{k/d}})$ with

$\nu :E\mapsto E^{\prime }$ the twisting isomorphism. On

$E^{\prime }({\mathbb{F}}_{p^{k/d}})$, there is an efficient endomorphism

$\psi$ called "untwist-Frobenius-twist"

$\psi ={\nu }^{-1}\circ {\pi }_p\circ \nu$ where

${\pi }_p$ is the

$p$-power Frobenius. It satisfies

${\psi }^2-t\psi +p=0$

BLS12 curves have a twist of degree 6. Associated with a choice of

$\xi \in {\mathbb{F}}_{q^{k/6}}$ s.t.

$x^6-\xi \in {\mathbb{F}}_{q^{k/6}}[X]$ is irreducible, the equation of

$E^{\prime }$ can be either

• $y^2=x^3+b/\xi$ and we call it a D-twist or
• $y^2=x^3+b.\xi$ and we call it a M-twist

For the D-type,

${\nu }^{-1}:(x,y)\mapsto ({\xi }^{1/3}x,{\xi }^{1/2}y)$,
and for the M-type

${\nu }^{-1}:(x,y)\mapsto ({\xi }^{2/3}x/\xi ,{\xi }^{1/2}y/\xi )$

So given that

$k=12$ and

$d=6$,

${\mathbb{G}}_2$ is over

${\mathbb{F}}_{p^2}$ and

${\pi }_p:(x,y)\mapsto (x^p,y^p)=(\overline{x},\overline{y})$ and

$\psi$ is

$$(x,y)\mapsto (\overline{x}\cdot c_1^{te},\overline{y}\cdot c_2^{te})$$

Related work

Using the endomorphism

$\varphi$ on

${\mathbb{G}}_{\mathbb{1}}$ and

$\psi$ on

${\mathbb{G}}_{\mathbb{2}}$, Sean Bowe [1] derived using LLL algorithm as in Fuentes et al.[2] and Budroni and Pintore[3] fast formulae to check that a point is on BLS12-381

${\mathbb{G}}_{\mathbb{1}}$ and

${\mathbb{G}}_{\mathbb{2}}$. The formulae are

• $P\in {\mathbb{G}}_{\mathbb{1}}⟺((z^2-1)/3)\cdot (2\varphi (P)-P-{\varphi }^2(P))-{\varphi }^2(P)=\mathrm{\infty }$
• $Q\in {\mathbb{G}}_{\mathbb{2}}⟺z\cdot {\psi }^3(Q)-{\psi }^2(Q)+Q=\mathrm{\infty }$

Observations

• To derive

  ${\mathbb{G}}_{\mathbb{1}}$ membership formula for BLS12, there is no need for LLL algorithm. Given the polynomials
  $r(x)$ and
  $\lambda (x)$, a simple formula can be derived
  
  $$r(z)\cdot P=(z^4-z^2+1)\cdot P=(z^2\cdot \lambda (z)+1)\cdot P=z^2\cdot \varphi (P)+P$$
  The formula in [1] can be simplified into this one by using the fact that
  ${\varphi }^2+\varphi +1=0$.

• For

  ${\mathbb{G}}_{\mathbb{2}}$, the check can be done the same way:
  $z^2\cdot \varphi (Q)+Q=\mathrm{\infty }$ (note
  $\varphi$ in
  ${\mathbb{G}}_{\mathbb{2}}$ uses the other cube root of unity
  $-\omega -1$). However, the formula in [1] is faster (multiplication by
  $z$ instead of
  $z^2$) but it can be simplified into
  $-z\cdot \psi (\varphi (Q))+\varphi (Q)+Q=0$ by remarking that
  ${\psi }^2=-\varphi$.

$\to$ Why

${\psi }^2=-\varphi$?
Let's take the example of D-twist, we have

$$\begin{gathered} {\nu }^{-1}:(x,y)\mapsto ({\xi }^{1/3}x,{\xi }^{1/2}y) \\ {\pi }_p:(x,y)\mapsto (y^p,y^p)=(\overline{x},\overline{y}) \\ \nu :(x,y)\mapsto (1/{\xi }^{1/3}x,1/{\xi }^{1/2}y) \\ \psi :(x,y)\mapsto ({\xi }^{(p-1)/3}\cdot \overline{x},{\xi }^{(p-1)/2}\cdot \overline{y}) \end{gathered}$$
and,

$${\psi }^2:(x,y)\mapsto ({\xi }^{(p+1)(p-1)/3}\cdot x,{\xi }^{(p+1)(p-1)/2}\cdot y)$$
Now, recal that

$x\mapsto x^{p+1}$ is the trace

${\mathbb{F}}_{p^2}/{\mathbb{F}}_p$ hence

$x^{p+1}\in {\mathbb{F}}_p$ and

$({\xi }^{(p-1)/6}{)}^{p+1}$ is a primitive 6th root of unity. So,

${\xi }^{(p+1)(p-1)/3}$ is primitive 3rd root of unity. Now,

$({\xi }^{(p-1)/2}{)}^{p+1}=({\xi }^{p+1}{)}^{(p-1)/2}$ and

${\xi }^{p+1}\in {\mathbb{F}}_p$, this is the trace. Finally,

$({\xi }^{p+1}{)}^{(p-1)/2}=\{\begin{array}{l}1\text{if square}\\ -1\text{otherwise}\end{array}$, and because

$\xi$ is not a square in

${\mathbb{F}}_{p^2}$, then

$({\xi }^{p+1}{)}^{(p-1)/2}=-1$, which means

$${\psi }^2:(x,y)\mapsto (\omega \cdot x,-y)=-\varphi$$

[NEW] Scott eprint 2021/1130

• For
  ${\mathbb{G}}_{\mathbb{1}}$, Scott proves by contradiction that checking the endorphism is sufficient:
  $\varphi (P)=-z^{2}P$. In fact,
  $-z^6\equiv \lambda \equiv 1\mathrm{mod}r$ because
  $\lambda$ a third root of unity in
  ${\mathbb{F}}_{\mathbb{r}}$. If the endomorphism was true for a point of order
  $c\cdot r$, then by CRT,
  $-z^6\equiv 1\mathrm{mod}c$ but
  $c\mid z-1$ for BLS curves and hence
  $u^6=1\mathrm{mod}c$.
• For
  ${\mathbb{G}}_{\mathbb{2}}$, he finds a simpler formula:
  $\psi (P)=zP$. In fact, given that
  $(p+1-t)Q=\mathrm{\infty }$ and
  $t=z+1$ then
  $uP=pQ$.
  $\psi$ verifies
  ${\psi }^2(Q)-t\psi (Q)+pQ=\mathrm{\infty }$ and this becomes
  $zQ=\psi (uQ)+\psi (Q)-{\psi }^2(Q)$ which has two solutions:
  $\psi (Q)=Q$ or
  $\psi (Q)=uQ$. Only the latter is valid sinc
  $\psi$ acts non-trivially on
  ${\mathbb{G}}_{\mathbb{2}}$.

Implementation

Example code for BLS12-381 (M-twist) with seed

$z=-15132376222941642752$ and BLS12-377 (D-twist) with

$z=9586122913090633729$ in gnark-crypto library (golang).

• BLS12-381
  ${\mathbb{G}}_1$ membership test
• BLS12-381
  ${\mathbb{G}}_2$ membership test
• BLS12-377
  ${\mathbb{G}}_1$ membership test
• BLS12-377
  ${\mathbb{G}}_2$ membership test