Computing the Optimal Ate Pairing over the BLS12-381 Curve

The post BLS12-381 For The Rest Of Us constitutes the base point for this article, so I highly recommend reading it to get a solid background of the BLS1-381 curve. This post will reuse some parts with an emphasy on the computational aspect of the optimal Ate pairing over such curve.

For those with a poor background on Pairing-Based Cryptography (PBC) but with a decent background on Elliptic-Curve Cryptoraphy (ECC) I recommend reading the following resources in order:

1. Pairings For Beginners.
2. Constructing Elliptic Curves with Prescribed Embedding Degrees.
3. BLS12-381: New zk-SNARK Elliptic Curve Construction.

Only after (and not before) you feel sufficiently comfortable with both PBC and ECC come back to this post and start to make sense out of it. The full list of consulted resources can be found at the end of this post.

The implementation in zkASM has been done in this PR.

The Curve

The BLS12-381 is the elliptic curve

$E$ of the form:

$$y^2=x^3+4$$
defined over a finite field

${\mathbb{F}}_p$, where the prime

$p$ is the following

$381$-bit number:

p = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787

The number of points

$\mathrm{\#}E({\mathbb{F}}_p)=p+1-t$ can be factorized as follows:

3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

where t = x + 1 = -15132376222941642751 is known as the trace of Frobenius and x is the BLS-family parameter that generates this specific curve.

Therefore, its

$255$-bit prime factor:

r = 52435875175126190479447740508185965837690552500527637822603658699938581184513

is the only one with sufficiently size for cryptographic purposes.

The point

$P\in E({\mathbb{F}}_p)$ with coordinates:

x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569

is a point of order

$r$, i.e. a generator of the subgroup of size

$r$ of the curve.

The embedding degree

$k$ of this curve is

$12$.

Tower of Extension Fields

To represent

${\mathbb{F}}_{p^{12}}$ we use the following tower of extension fields:
fields:

$$\begin{array}{rl}{\mathbb{F}}_{p^2}& ={\mathbb{F}}_p[u]/(u^2-\beta ),\\ {\mathbb{F}}_{p^6}& ={\mathbb{F}}_{p^2}[v]/(v^3-\xi ),\\ {\mathbb{F}}_{p^{12}}& ={\mathbb{F}}_{p^6}[w]/(w^2-v),\end{array}$$
where

$\beta$ is not a quadratic residue in

${\mathbb{F}}_p$ and

$\xi$ is neither a quadratic residue or a cubic residue in

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

In the particular case of the BLS12-381, we have

$\beta =-1$ and

$\xi =1+u$ and therefore:

$$\begin{array}{rl}{\mathbb{F}}_{p^2}& ={\mathbb{F}}_p[u]/(u^2+1),\\ {\mathbb{F}}_{p^6}& ={\mathbb{F}}_{p^2}[v]/(v^3-(1+u)),\\ {\mathbb{F}}_{p^{12}}& ={\mathbb{F}}_{p^6}[w]/(w^2-v),\end{array}$$

from which we can extract the identities

$u^2=-1$,

$w^2=v$,

$v^3=1+u$ and consequently the idenity

$w^6=1+u$.

Using the latter identity, we can also write:

$${\mathbb{F}}_{p^{12}}={\mathbb{F}}_{p^2}[w]/(w^6-(1+u))$$

These two representations of

${\mathbb{F}}_{p^{12}}$ will allow us to apply some optimizations:

1. Writing any element
   $f\in {\mathbb{F}}_{p^{12}}$ as
   $f=g+hw$, with
   $g,h\in {\mathbb{F}}_{p^6}$ implies
   $f^{p^6}=\overline{f}=g-hw$. Thus, computing the
   $p^6$-th power of any element in
   ${\mathbb{F}}_{p^{12}}$ is computationally "free".
2. Now, if we write
   $g=g_0+g_{1}v+g_2{v}^2$ and
   $h=h_0+h_{1}v+h_2{v}^2$ where
   $g_0$,
   $g_1$,
   $g_2$,
   $h_0$,
   $h_1$,
   $h_2\in {\mathbb{F}}_{p^2}$ we have:
   
   $$f=g_0+h_{0}w+g_1{w}^2+h_1{w}^3+g_2{w}^4+h_2{w}^5,$$
   which will allow us to compute
   $f^p$ and
   $f^{p^2}$ (needed for the final exponentiation) very efficiently.

Twist

BLS curves admits a sextic twist

$E^{\prime }$ defined over

${\mathbb{F}}_{p^2}$ of the form:

$$y^{\prime 2}=x^{\prime 3}+4·(1+u).$$

This means that pairing computations can be restricted to points

$P\in E({\mathbb{F}}_p)$ and

$Q\in E^{\prime }({\mathbb{F}}_{p^2})$ and avoid computations over

${\mathbb{F}}_{p^{12}}$ entirely.

The point

$P\in E^{\prime }({\mathbb{F}}_{p^2})$ with coordinates:

x = 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160 + 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758·u
y = 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905 + 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582·u

is a point of order

$r$, i.e. a generator of the subgroup of size

$r$ of the curve.

The following mapping, known as the untwist:

$$\phi (x^{\prime },y^{\prime })=(x^{\prime }/w^2,y^{\prime }/w^3)$$
with:

1/w^2 = (2001204777610833696708894912867952078278441409969503942666029068062015825245418932221343814564507832018947136279894 + 2001204777610833696708894912867952078278441409969503942666029068062015825245418932221343814564507832018947136279893·u)·w^4
1/w^3 = (2001204777610833696708894912867952078278441409969503942666029068062015825245418932221343814564507832018947136279894 + 2001204777610833696708894912867952078278441409969503942666029068062015825245418932221343814564507832018947136279893·u)·w^3

defines a group isomorphism from

$E^{\prime }({\mathbb{F}}_{p^2})[r]$ to

$E({\mathbb{F}}_{p^{12}})[r]\cap \text{Ker}({\pi }_p-[p])$ and we are going to use it to convert points from the twisted curve

$E^{\prime }$ to the curve

$E$ only whenever required.

The inverse mapping, the twist, is defined as:

$${\phi }^{-1}(x^{\prime },y^{\prime })=(x^{\prime }{w}^2,y^{\prime }{w}^3).$$

The Pairing

The optimal Ate pairing

$e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$ over the BLS12-381 curve is defined by:

$$e(P,Q)={\overline{f_{|x|,Q}(P)}}^{\frac{p^{12}-1}{r}}$$
where:

• ${\mathbb{G}}_1=E({\mathbb{F}}_p)[r]$ is the only subgroup of the
  $r$-torsion of
  $E$ over
  ${\mathbb{F}}_p$.

• ${\mathbb{G}}_2=E({\mathbb{F}}_{p^{12}})[r]\cap \text{Ker}({\pi }_p-[p])$, represented for point arithmetic efficiency by
  $E^{\prime }({\mathbb{F}}_{p^2})[r]$. The former is the trace zero subgroup of the
  $r$-torsion of
  $E$ over
  ${\mathbb{F}}_{p^{12}}$, whereas the latter is the only subgroup of the
  $r$-torsion of
  $E^{\prime }$ over
  ${\mathbb{F}}_{p^2}$.

• ${\mathbb{G}}_T={\mu }_r$ is the set of
  $r$-th roots of unity over
  ${\mathbb{F}}_{p^{12}}^{\ast }$.

• x = -15132376222941642752, which is a number of

  $64$ bits that can be expressed in binary as:
  ​​2^63 + 2^62 + 2^60 + 2^57 + 2^48 + 2^16
  ​​[1,1,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
  ​​0b1101001000000001000000000000000000000000000000010000000000000000
  

  and has a Hamming weight of 6.

• $f_{i,Q}$, for any
  $i\in \mathbb{N}$ and
  $Q\in {\mathbb{G}}_2$, is a
  ${\mathbb{F}}_{p^{12}}$ rational function on
  $E$ that is computed using Miller's "double-and-add"-style algorithm:
  
  $$\begin{array}{r}{f}_{i+j,Q}=f_{i,Q}\cdot f_{j,Q}\cdot \frac{{\ell }_{[i]\phi (Q),[j]\phi (Q)}}{v_{[i+j]\phi (Q)}},\\ f_{i+1,Q}=f_{m,Q}\cdot \frac{{\ell }_{[i]\phi (Q),\phi (Q)}}{v_{[i+1]\phi (Q)}},\end{array}$$
  starting with
  $f_{1,Q}=1$.

The conjugate of an element in

$f=a+bw$ in

${\mathbb{F}}_{p^{12}}$ is

$\overline{f}=a-bw$. Hence, if we write

$f=g_0+h_{0}w+g_1{w}^2+h_1{w}^3+g_2{w}^4+h_2{w}^5$ we have:

$$\overline{f}=g_0-h_{0}w+g_1{w}^2-h_1{w}^3+g_2{w}^4-h_2{w}^5.$$

Therefore, what we want to compute is the following:

def e(P,Q):
    assert(subgroup_check_G1(P))
    assert(subgroup_check_G2(Q))
    if ((P == 0) or (Q == 0)) return 1 # Here, 0 represents the 
                                       # point at infinity
    R = Q
    f = 1
    for i in range(len(x)-2,-1,-1):
        f = f * f * line(untwist(R),untwist(R),P)
        R = 2 * R
        if x[i] == 1:
            f = f * line(untwist(R),untwist(Q),P)
            R = R + Q

    return final_exponentiation(conjugate(f))

In what follows we explain how to compute each of the components of the previous pseudocode snippet.

Subgroup Checks

To summary 2019/814, we have:

• A point

  $P\in E({\mathbb{F}}_p)$ belongs to
  ${\mathbb{G}}_1=E({\mathbb{F}}_p)[r]$ if and only if:
  
  $$\left[\frac{x^2-1}{3}\right]([2]\sigma (P)-P-{\sigma }^2(P))={\sigma }^2(P)$$
  where
  $\sigma :E({\mathbb{F}}_p)\to E({\mathbb{F}}_p)$ is the well-known endomorphism^[1] defined by
  $(a,b)\to (\gamma ·a,b)$, where
  $\gamma \in {\mathbb{F}}_p^{\ast }$ is of order
  $3$.
  ​​​​𝛄 = 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939436
  

  This is clearly much cheaper than the naive scalar multiplication by

  $r$, since its main cost is the scalar multiplication by
  $(x^2-1)/3$, which is half the size of
  $r$ and has low Hamming weight.

• A point

  $Q\in E^{\prime }({\mathbb{F}}_{p^2})$ belongs to
  ${\mathbb{G}}_2=E^{\prime }({\mathbb{F}}_{p^2})[r]$ if and only if:
  
  $$[x]{\psi }^3(Q)+Q={\psi }^2(Q)$$
  where
  $\psi :E^{\prime }({\mathbb{F}}_{p^2})\to E^{\prime }({\mathbb{F}}_{p^2})$ is the untwist-Frobenius-twist endomorphism, i.e.,
  $\psi :={\phi }^{-1}{\pi }_p\phi$.

  Again, this is much cheaper than the naive scalar multiplication by

  $r$, since its main cost is the scalar multiplication by
  $x$, which is roughly a fourth the size of
  $r$.

Line Equations

Different Points

Given two points

$Q_1=(x_1^{\prime },y_1^{\prime })$ and

$Q_2=(x_2^{\prime },y_2^{\prime })$ in the twisted curve

$E^{\prime }({\mathbb{F}}_{p^2})$ such that

$x_1^{\prime }\ne y_1^{\prime }$ and

$x_2^{\prime }\ne y_2^{\prime }$ and a point

$P=(x,y)$ in the curve

$E({\mathbb{F}}_p)$, the evaluation at

$P$ of the line passing through

$\phi (Q_1)$ and

$\phi (Q_2)$ is given by:

$${\ell }_{\phi (Q_1),\phi (Q_2)}(P)=(x_1^{\prime }{y}_2^{\prime }-x_2^{\prime }{y}_1^{\prime })+w^2(y_1^{\prime }-y_2^{\prime })x+w^3(x_2^{\prime }-x_1^{\prime })y$$

The Same Points

Given a point

$Q=(x^{\prime },y^{\prime })$ in the twisted curve

$E^{\prime }({\mathbb{F}}_{p^2})$ and a point

$P=(x,y)$ in the curve

$E({\mathbb{F}}_p)$, the evaluation at

$P$ of the line passing through

$\phi (Q)$ is given by:

$${\ell }_{\phi (Q),\phi (Q)}(P)=w(3x^{\prime 3}-2y^{\prime 2})+w^3(-3x{x}^{\prime 2})+w^4(2y{y}^{\prime })$$

Final Exponentiation

In the final exponentiation, we raise an element

$f\in {\mathbb{F}}_{p^{12}}$ to the power

$(p^{12}-1)/r$.

First, divide the exponent as follows:

$$\frac{p^{12}-1}{r}=\underset{\text{easy part}}{\underbrace{(p^6-1)(p^2+1)}}\underset{\text{hard part}}{\underbrace{\frac{p^4-p^2+1}{r}}}$$

The Easy Part

Let's start with the easy part of the easy part, when we first attempt to compute

$f^{p^6-1}$. But since,

$f^{p^6}=\overline{f}$, we have

$f^{p^6-1}=\overline{f}\cdot f^{-1}$, just one conjugate, one inversion and one multiplication in

${\mathbb{F}}_{p^{12}}$.

To finish the easy part, we first compute

$(f^{(p^6-1)}{)}^{p^2}$ which is the Frobenius operator applied to

$f^{p^6-1}$ and then multiply the result by

$f^{p^6-1}$ to finally obtain

$m:=f^{(p^6-1)(p^2+1)}\in {\mathbb{F}}_{p^{12}}$.

Importantly, after the computation of the easy part, the resulting field element becomes a member of the cyclotomic subgroup

${\mathbb{G}}_{{\varphi }_6(p^2)}={\mathbb{G}}_{{\varphi }_{12}(p)}=\{a\in {\mathbb{F}}_{p^{12}}\mid a^{{\varphi }_{12}(p)}=a^{p^4-p^2+1}=a^{p^6+1}=1\}$, which means that inversion from now on can be computed by simply conjugation. Moreover, when an element

$a$ belongs to

${\mathbb{G}}_{{\varphi }_6(p^2)}$, one can compute

$a^2$ using fewer multiplications and therefore the overall costs of performing exponentiations (see this section).

The Hard Part

Following Section 5 of this 2020/875, we can write:

$$\frac{p^4-p^2+1}{r}=\frac{(|x|+1{)}^2\cdot (p-|x|)\cdot (x^2+p^2-1)}{3}+1.$$

To compute it, we proceed as follows:

def hard_part(m):
    x = abs(x)
    
    # 1] m^{(x+1)/3}
    y1 = m**((x+1)/3)
    
    # 2] m^{(x+1)^2/3}
    y2 = y1**(x+1)
    
    # 3.1] m^{(x+1)^2/3*-x}
    y31 = conjugate(y2)**x
    
    # 3.2] m^{(x+1)^2/3*p}
    y32 = Frobenius1(y2)
    
    # 4] m^{(x+1)^2/3*(p-x)}
    y4 = y31*y32
    
    # 5.1] m^{(x+1)^2/3*(p-x)*x^2}
    y51 = (y4**x)**x
    
    # 5.2] m^{(x+1)^2/3*(p-x)*p^2}
    y52 = Frobenius2(y4)
    
    # 5.3] m^{(x+1)^2/3*(p-x)*-1}
    y53 = conjugate(y4)
    
    # 6] m^{(x+1)^2/3*(p-x)*(x^2+p^2)}
    y6 = y51*y52
    
    # 7] m^{(x+1)^2/3*(p-x)*(x^2+p^2-1)}
    y7 = y6*y53
    
    # 8] m^{(x+1)^2/3*(p-x)*(x^2+p^2-1)+1}
    y8 = y7*m

    return y8

(recall that, at this point, computing the conjugate is the same as computing the inverse)

Frobenius Operator

As we have shown, in the final exponentation we must compute the first and second Frobenius operator

${\pi }_p,{\pi }_p^2$ over an element in

${\mathbb{F}}_{p^{12}}$. Recalling that

${\pi }_p^i(x)=x^{p^i}$, a naive implementation would take

$O(\log p)$

${\mathbb{F}}_{p^{12}}$-operations, but we will do it much better.

Recall that we can write any element

$f\in {\mathbb{F}}_{p^{12}}$ as:

$$f=g+hw=g_0+h_{0}w+g_1{w}^2+h_1{w}^3+g_2{w}^4+h_2{w}^5$$
where

$g=g_0+g_{1}v+g_2{v}^2$ and

$h=h_0+h_{1}v+h_2{v}^2$ with

$g,h\in {\mathbb{F}}_{p^6}$ and

$g_i,h_i\in {\mathbb{F}}_{p^2}$.

Then, we have:

$$\begin{array}{r}{f}^p={\overline{g}}_0+{\overline{h}}_0{\gamma }_{1,1}w+{\overline{g}}_1{\gamma }_{1,2}{w}^2+{\overline{h}}_1{\gamma }_{1,3}{w}^3+{\overline{g}}_2{\gamma }_{1,4}{w}^4+{\overline{h}}_2{\gamma }_{1,5}{w}^5,\\ f^{p^2}=g_0+h_0{\gamma }_{2,1}w+g_1{\gamma }_{2,2}{w}^2+h_1{\gamma }_{2,3}{w}^3+g_2{\gamma }_{2,4}{w}^4+h_2{\gamma }_{2,5}{w}^5,\end{array}$$
with

${\gamma }_{1,i}=(1+u{)}^{i\frac{p-1}{6}}$ and

${\gamma }_{2,i}=(1+u{)}^{i\frac{p^2-1}{6}}={\gamma }_{1,i}\cdot {\overline{\gamma }}_{1,i}$.

Expand to see the proof

We will now show that raising an

${\mathbb{F}}_{p^2}$-element over any power of

$p$ is almost cost free and therefore so is raising

$f$.

• Take
  $b=b_0+b_{1}u\in {\mathbb{F}}_{p^2}$ with
  $b_0,b_1\in {\mathbb{F}}_p$. Then,
  $b^{p^{2i}}=b_0+b_1(u^{(p^2{)}^i})=b_0+b_{1}u=b$ from Lagrange theorem. Similarly,
  $b^{p^{2i-1}}=\frac{b^{p^{2i}}}{b^{p^2}\cdot b^p}=\frac{b}{b\cdot b^{-p}}=\frac{1}{b^{-p}}=b^p=\overline{b}$.
• Notice
  $w^p=(w^6{)}^{\frac{p-1}{6}}w=(1+u{)}^{\frac{p-1}{6}}w$ and therefore
  $(w^i{)}^p={\gamma }_{1,i}{w}^i$, where
  ${\gamma }_{1,i}=(1+u{)}^{i\frac{p-1}{6}}$.

Using all the previous observations, we have:

$$\begin{array}{rl}{f}^p& =(g_0+h_{0}w+g_1{w}^2+h_1{w}^3+g_2{w}^4+h_2{w}^5{)}^p\\ & ={\overline{g}}_0+{\overline{h}}_0{w}^p+{\overline{g}}_1{w}^{2p}+{\overline{h}}_1{w}^{3p}+{\overline{g}}_2{w}^{4p}+{\overline{h}}_2{w}^5\\ & ={\overline{g}}_0+{\overline{h}}_0{\gamma }_{1,1}w+{\overline{g}}_1{\gamma }_{1,2}{w}^2+{\overline{h}}_1{\gamma }_{1,3}{w}^3+{\overline{g}}_2{\gamma }_{1,4}{w}^4+{\overline{h}}_2{\gamma }_{1,5}{w}^5,\end{array}$$
which can be computed using a few multiplications and a few conjugations, assuming each

${\gamma }_{1,i}$ is pre-computed for

$i\in [5]$.

Similarly, notice

$w^{p^2}=(1+u{)}^{\frac{p^2-1}{6}}w=({\gamma }_{1,1}{)}^{1+p}w={\gamma }_{1,1}\cdot {\overline{\gamma }}_{1,1}w$ and therefore

$(w^i{)}^{p^2}={\gamma }_{2,i}{w}^i$, where

${\gamma }_{2,i}={\gamma }_{1,i}\cdot {\overline{\gamma }}_{1,i}$.

Hence, assuming the precomputation of

${\gamma }_{1,i},{\gamma }_{2,i}$ for

$i\in [5]$, we can compute

$f^p$ and

$f^{p^2}$ almost for free.

Speeding up Exponentiations in the Cyclotomic Subgroup

I follow 2010/542 closely for this section.

Recall that:

$$\begin{array}{rl}{\mathbb{F}}_{p^2}& ={\mathbb{F}}_p[u]/(u^2+1),\\ {\mathbb{F}}_{p^6}& ={\mathbb{F}}_{p^2}[v]/(v^3-(1+u)),\\ {\mathbb{F}}_{p^{12}}& ={\mathbb{F}}_{p^6}[w]/(w^2-v).\end{array}$$
and also:

$${\mathbb{F}}_{p^{12}}={\mathbb{F}}_{p^2}[w]/(w^6-(1+u))$$

For this optimitzation, it will be useful to introduce

${\mathbb{F}}_{p^4}$ and represent

${\mathbb{F}}_{p^{12}}$ as a degree-3 extension of

${\mathbb{F}}_{p^4}$:

$$\begin{array}{rl}{\mathbb{F}}_{p^4}& ={\mathbb{F}}_{p^2}[V]/(V^2-(1+u)),\\ {\mathbb{F}}_{p^{12}}& ={\mathbb{F}}_{p^4}[w]/(w^3-V),\end{array}$$
where

$V=w^3$; so that an element

$f$ in

${\mathbb{F}}_{p^{12}}$ can be written as

$f=(g_0+g_{1}V)+(g_2+g_{3}V)w+(g_4+g_{5}V)w^2$. We can equivalently write

$f=g_0+g_{2}w+g_4{w}^2+g_1{w}^3+g_3{w}^4+g_5{w}^5$.

These optimizations are due to "compression" and "decompression" techniques, which exploits the algebraic relationships arising from elements belonging to the cyclotomic subgroup

${\mathbb{G}}_{{\varphi }_6(p^2)}$.

Compression and Decompression

If

$f=g_0+g_{2}w+g_4{w}^2+g_1{w}^3+g_3{w}^4+g_5{w}^5\in {\mathbb{G}}_{{\varphi }_6(p^2)}$ then the compression function

$\mathcal{C}$ is:

$$\mathcal{C}(f)=[g_2,g_3,g_4,g_5].$$
and the decompression function

$\mathcal{D}$ is:

$$\mathcal{D}([{\tilde{g}}_2,{\tilde{g}}_3,{\tilde{g}}_4,{\tilde{g}}_5])={\tilde{g}}_0+{\tilde{g}}_{2}w+{\tilde{g}}_4{w}^2+{\tilde{g}}_1{w}^3+{\tilde{g}}_3{w}^4+{\tilde{g}}_5{w}^5,$$
where:

$$\{\begin{array}{ll}{\tilde{g}}_1=\frac{{\tilde{g}}_5^2(1+u)+3{\tilde{g}}_4^2-2{\tilde{g}}_3}{4{\tilde{g}}_2},{\tilde{g}}_0=(2{\tilde{g}}_1^2+{\tilde{g}}_2{\tilde{g}}_5-3{\tilde{g}}_3{\tilde{g}}_4)(1+u)+1,& \text{if }{\tilde{g}}_2\ne 0\\ {\tilde{g}}_1=\frac{2{\tilde{g}}_4{\tilde{g}}_5}{{\tilde{g}}_3},{\tilde{g}}_0=(2{\tilde{g}}_1^2-3{\tilde{g}}_3{\tilde{g}}_4)(1+u)+1,& \text{if }{\tilde{g}}_2=0\end{array}$$

Compressed Squaring

Now, on input

$f\in {\mathbb{G}}_{{\varphi }_6(p^2)}$ we will be able to compute its square on compressed form. That is,

$\mathcal{C}(f^2)=[h_2,h_3,h_4,h_5]$, where

$h=f^2=h_0+h_{2}w+h_4{w}^2+h_1{w}^3+h_3{w}^4+h_5{w}^5$:

$$\begin{array}{rl}{h}_2& =2(g_2+3(1+u)B_{4,5}),\\ h_3& =3(A_{4,5}-(2+u)B_{4,5})-2g_3,\\ h_4& =3(A_{2,3}-(2+u)B_{2,3})-2g_4,\\ h_5& =2(g_5+3B_{2,3}),\\ A_{i,j}& =(g_i+g_j)(g_i+(1+u)g_j),\\ B_{i,j}& =g_i\cdot g_j.\end{array}$$

Exponentiation in the Cyclotomic Subgroup

Given

$f\in {\mathbb{G}}_{{\varphi }_6(p^2)}\subset {\mathbb{F}}_{p^{12}}^{\ast }$ and

$e\ge 1$, the idea is to compute

$f^e$ using the squaring formula in compressed form.

Represent

$e$ in binary as

$e=e_{\ell -1}{e}_{\ell -2}\dots e_1{e}_0$ with

$e_{\ell -1}=1$ and define

$H_e=\{i:1\le i\le \ell -1\text{ and }{e}_i=1\}$. Then:

$$f^e=\prod _{i=0}^{\ell -1}{f}^{e_i\cdot 2^i}=\prod _{i=0}^{\ell -1}(f^{2^i}{)}^{e_i}=f^{e_0}\prod _{i\in H_e}\mathcal{D}(\mathcal{C}(f{)}^{2^i}).$$

Therefore, we can use the square-and-multiply algorithm to compute such product. Since we are going to be squaring in compressed form, we start at

$\mathcal{C}(f)$ rather than the standard

$f$ in such algorithm.

def exp_cyclo(f,e):
    Cf = comp(f);
    result = 1;
    for i in range(len(e)):
        if (e[i] == 1) {
            result = decomp(Cf) * result;
        }

        Cf = square_comp(Cf);
    }

    return result;

Resources

• BLS12-381 For The Rest Of Us
• Constructing Elliptic Curves with Prescribed Embedding Degrees
• BLS12-381: New zk-SNARK Elliptic Curve Construction
• Draft IETF standard for pairing-friendly curves
• Zcash code
• Faster Subgroup Checks for BLS12-381
• Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms
• Efficient Final Exponentiation via Cyclotomic Structure for Pairings over Families of Elliptic Curves
• Squaring in Cyclotomic Subgroups

---

1. The endomorphism

   $\sigma$ acts as a multiplication map
   $[\lambda ]P$, where
   $\lambda =t^2-1$. ↩︎