Computing the Optimal Ate Pairing over the BN254 Curve

The post BN254 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 BN254 curve. This post will reuse some parts with an emphasy on the computational aspect of the optimal Ate pairing over the BN254 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. Pairing-Friendly Elliptic Curves of Prime Order.
3. High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves.

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 implementation in zkASM can be found here.

The Curve

The BN254 is the elliptic curve $E$ of the form:

defined over a finite field $\mathbb{F}_p$, where the prime $p$ is the following $254$-bit number:

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

The number of points $\#E(\mathbb{F}_p) = p+1-t$ happens to also be a prime $r$ of $254$ bits:

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

where t = 147946756881789318990833708069417712967 is known as the trace of Frobenius.

The point $(1,2) \in E(\mathbb{F}_p)$ is a point of order $r$, i.e. a generator of the group of points of the curve. In fact, all points in $E(\mathbb{F}_p)\backslash\{\mathcal{O}\}$ are generators, as Lagrange’s Theorem shows.

The embedding degree $k$ of this curve is $12$.

For more information, refer to BN254 For The Rest Of Us or the EIPs 196 and 197.

Tower of Extension Fields

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

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 BN254, we have $\beta = -1$ and $\xi = 9+u$ and therefore:

from which we can extract the identities $u^2 = -1$, $w^2 = v$, $v^3 = 9+u$ and consequently the idenity $w^6 = 9+u$.

Using the latter identity, we can also write:

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 + h w$, with $g,h \in \mathbb{F}_{p^{6}}$ implies ¹ $f^{p^6} = \bar{f} = g - h w$. 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_1v + g_2v^2$ and $h = h_0 + h_1v + h_2v^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_0w + g_1w^2 + h_1w^3 + g_2w^4 + h_2w^5,$$ which will allow us to compute $f^p,f^{p^2}$ and $f^{p^3}$ (needed for the final exponentiation) very efficiently.

Twist

BN curves admits a sextic twist $E'$ defined over $\mathbb{F}_{p^2}$ of the form:

or more specifically:

(y')² = (x')³ + (19485874751759354771024239261021720505790618469301721065564631296452457478373 + 266929791119991161246907387137283842545076965332900288569378510910307636690·u)

This means that pairing computations can be restricted to points $P \in E(\mathbb{F}_p)$ and $Q \in E'(\mathbb{F}_{p^2})$ and avoid computations over $\mathbb{F}_{p^{12}}$ entirely.

The number of points of $E'$ is:

which concrete to:

#E' = 479095176016622842441988045216678740799252316531100822436447802254070093686356349204969212544220033486413271283566945264650845755880805213916963058350733
c = 21888242871839275222246405745257275088844257914179612981679871602714643921549

The mapping

defines a group homomorphism from $E'(\mathbb{F}_{p^2})$ to $E(\mathbb{F}_{p^{12}})$ and we are going to use it to send points from the twisted curve $E'$ to the curve $E$ (but not the other way around).

The Pairing

The optimal Ate pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ over the BN254 curve is defined by:

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^2})[r]$ is the only subgroup of the $r$-torsion of $E'$ over $\mathbb{F}_{p^2}$.

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

• x = 4965661367192848881 and therefore 6x+2 = 29793968203157093288, which is a number of $65$ bits that can be expressed in the base $\{-1,0,1\}$ as follows:

  2^3 + 2^5 - 2^7 + 2^10 - 2^11 + 2^14 + 2^17 + 2^18 - 2^20 + 2^23 - 2^25 + 2^30 + 2^31 + 2^32 - 2^35 + 2^38 - 2^44 + 2^47 + 2^48 - 2^51 + 2^55 + 2^56 - 2^58 + 2^61 + 2^63 + 2^64
  [0, 0, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 1, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0, -1, 0, 0, 0, 0, 1, 1, 1, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0, 1, 1]
  0001010-1001-100100110-10010-1000011100-100100000-1001100-1000110-1001011

  which has a Hamming weight of 26.

  We prefer base $\{-1,0,1\}$ over base $\{0,1\}$ because 6x+2 expressed in the latter is:

  2^3 + 2^5 + 2^7 + 2^8 + 2^9 + 2^11 + 2^12 + 2^13 + 2^17 + 2^18 + 2^20 + 2^21 + 2^22 + 2^25 + 2^26 + 2^27 + 2^28 + 2^29 + 2^31 + 2^32 + 2^35 + 2^36 + 2^37 + 2^44 + 2^45 + 2^46 + 2^48 + 2^51 + 2^52 + 2^53 + 2^54 + 2^56 + 2^58 + 2^59 + 2^60 + 2^63 + 2^64 
  [0,0,0,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,1,0,0,1,1,1,1,0,1,0,1,1,1,0,0,1,1]
  00010101110111000110111001111101100111000000111010011110101110011

  which has a Hamming weigth of 37.

I moved from base $\{0,1\}$ to base $\{-1,0,1\}$ by using the identity² $2^{n+1} - 2^m = 2^n + 2^{n-1} + ... + 2^m,$ that holds for any $n,m \in \mathbb{N}$ such that $n \geq m$. In words, it is unpacking groups of $1$‘s of any size to a single $1$ and $-1$ in the binary decomposition.

• $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{aligned} f_{i+j,Q} = f_{i,Q} \cdot f_{j,Q} \cdot \frac{\ell_{[i]\Psi(Q),[j]\Psi(Q)}}{v_{[i+j]\Psi(Q)}}, \\ f_{i+1,Q} = f_{m,Q} \cdot \frac{\ell_{[i]\Psi(Q),\Psi(Q)}}{v_{[i+1]\Psi(Q)}}, \\ \end{aligned}$$ starting with $f_{1,Q} = 1$.
• $\ell_{P_1,P_2}$ denotes the equation of a line passing through $P_1$ and $P_2$ while $v_{P}$ denotes the equation of a vertical line passing through $P$. However, due to the final exponentiation, the value of $e(P,Q)$ remains unchanged if we omit the division by the vertical lines, so we will not care about such computation.
• $\pi_p^i(x,y) = (x^{p^i},y^{p^i})$ is known as the Frobenius operator.

Therefore, what we want to compute is the following:

bound = [0, 0, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 1, 0, 0, 1, 1, 0, -1,
         0, 0, 1, 0, -1, 0, 0, 0, 0, 1, 1, 1, 0, 0, -1, 0, 0, 1, 0, 0, 0,
         0, 0, -1, 0, 0, 1, 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0,
         1, 1] 

1101111010011011000001001001000111011101011100001011001111110111111100000111110100101101000001011101000011111001111110101000110

         # This is 6x+2 in base {-1,0,1}, which has a Hamming weight of 26

def e(P,Q):
    assert(subgroup_check_G1(P))
    assert(subgroup_check_G2(Q))
    if ((P == 0) or (Q == 0)) return 1 # Here, 0 is the identity element of E
    
    R = Q
    f = 1
    for i in range(len(bound)-2,-1,-1): # len(bound)=65
        f = f * f * line(twist(R),twist(R),P)
        R = 2 * R
        if bound[i] == 1:
            f = f * line(twist(R),twist(Q),P)
            R = R + Q
        elif bound[i] == -1:
            f = f * line(twist(R),twist(-Q),P)
            R = R - Q
            
    Qp = FrobEndo(Q); # Q'
    f = f * line(twist(R), twist(Qp), P);
    R = R + Qp;
    Qpp = -FrobEndo(Qp); # Q''
    f = f * line(twist(R), twist(Qpp), P);

    return final_exponentiation(f)

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

Subgroup Checks

To summary BN254 For The Rest Of Us, we have:

• $P \in \mathbb{G}_1 = E(\mathbb{F}_p)[r]$ if and only if $P \in E(\mathbb{F}_p)$. That is, if we write $P = (x,y)$ then we simply need to ensure that the equation $y^2 = x^3 + 3$ holds over $\mathbb{F}_p$.

  Costs: $2s + 1m + 1a$

• A point $Q = (x',y') \in E'(\mathbb{F}_{p^2})$ belongs to $\mathbb{G}_2 = E'(\mathbb{F}_{p^2})[r]$ if and only if:

  $$[x+1]Q + \psi([x]Q) + \psi^2([x]Q) = \psi^3([2x]Q)$$

  where $\psi : E'(\mathbb{F}_{p^2}) \to E'(\mathbb{F}_{p^2})$ is defined as $\psi(x',y') = ({\gamma_{1,2}}\bar{x}',\gamma_{1,3}\bar{y}')$, where $\gamma_{1,2} = (9+u)^{\frac{p-1}{3}},\gamma_{1,3} = (9+u)^{\frac{p-1}{2}}$.

  This was proven in 2022/348 and it is clearly much faster than the naive check $[r]Q = \mathcal{O}$, since $x \ll r$.

Costs: $2\tilde{c} + 2\tilde{m} + \text{cost of } [6x^2]P$

Line Equations

Different Points

Given two points $Q_1 =(x_1',y_1')$ and $Q_2=(x_2',y_2')$ in the twisted curve $E'(\mathbb{F}_{p^2})$ such that $x_1' \neq y_1'$ and $x_2' \neq y_2'$ and a point $P=(x,y)$ in the curve $E(\mathbb{F}_p)$, the evaluation at $P$ of the line passing through $\Psi(Q_1)$ and $\Psi(Q_2)$ is given by:

Costs: $3\tilde{a} + 2\tilde{m} + 4m$

The Same Points

Given a point $Q =(x',y')$ in the twisted curve $E'(\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 $\Psi(Q)$ is given by:

Costs: $1\tilde{a} + 2\tilde{s} + 2\tilde{m} + 10m$

The Last two Lines

Now we explain some tricks for the computation of the lines:

• For the first line notice that if $Q = (x',y') \in E'(\mathbb{F}_{p^2})$, then: $$\pi_p(\Psi(Q)) = ((w^2x')^p,(w^3y')^p) = (w^2(\gamma_{1,2}x'^p),w^3(\gamma_{1,3}y'^p)) = \Psi(\gamma_{1,2}x'^p,\gamma_{1,3}y'^p) = \Psi({\gamma_{1,2}}\bar{x}',\gamma_{1,3}\bar{y}'),$$ where $\gamma_{1,2} = (9+u)^{\frac{p-1}{3}},\gamma_{1,3} = (9+u)^{\frac{p-1}{2}}$ are precomputed.

The conjugate of an element in $f = a + bu$ in $\mathbb{F}_{p^2}$ is $\bar{f} = a -bu$.

Moreover, due to $\Psi$ being an homomorphism we have that $[n]\Psi(Q) = \Psi([n]Q)$ for all $n \in \mathbb{F}_r$. Consequently, we compute $\ell_{\Psi([6x+2]Q),\Psi(Q')}(P)$ as in the previous section, with $Q' = ({\gamma_{1,2}}\bar{x}',\gamma_{1,3}\bar{y}') = (x_1,y_1)$ (it's a good exercise to check that $Q'$ belongs to $E$).

**Costs:** $\underbrace{2\tilde{c} + 2\tilde{m}}_{Q'} + \ell_{\text{diff}}$

I don’t include the cost of computing $[6x+2]Q$, since it is obtained in the Miller loop.

• For the second line we similarly have:

  $$-\pi_p^2(\Psi(Q)) = -\pi_p(\pi_p(\Psi(Q))) = -\pi_p(\Psi(x_1,y_1)) = \Psi(\gamma_{1,2}\bar{x_1},-\gamma_{1,3}\bar{y_1})$$

  Again, due to the homomorphic property of $\Psi$, we compute $\ell_{\Psi([6x+2]Q + Q'),\Psi(Q'')}(P)$ as in the previous section, with $Q'' = (\gamma_{1,2}\bar{x_1},-\gamma_{1,3}\bar{y_1})$ (again, check that $Q''$ belongs to $E$).

  Costs: $1E'_{\text{add}} + \underbrace{2\tilde{c} + 2\tilde{m} + 2m}_{Q''} + \ell_{\text{diff}}$

Hence, in both cases, the Frobenius operator comes for free.

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:

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} = \bar{f}$, we have $f^{p^6 - 1} = \bar{f} \cdot f^{-1}$, just one conjugate, one inversion and one multiplication in $\mathbb{F}_{p^{12}}$.

The conjugate of an element in $f = a + bw$ in $\mathbb{F}_{p^{12}}$ is $\bar{f} = a -bw$. Hence, if we write $f = g_0 + h_0w + g_1w^2 + h_1w^3 + g_2w^4 + h_2w^5$ we have:

$$\bar{f} = g_0 - h_0w + g_1w^2 - h_1w^3 + g_2w^4 - h_2w^5.$$

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}_{\phi_{6}(p^2)} = \mathbb{G}_{\phi_{12}(p)} = \{a \in \mathbb{F}_{p^{12}} \mid a^{\phi_{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}_{\phi_{6}(p^2)}$, one can compute $a^2$ using fewer multiplications and therefore the overall costs of performing exponentiations (see this section).

Costs: $\underbrace{1C + 1I + 1M}_{f^{p^6-1}} + 5\tilde{m} + 1M$

The Hard Part

Following Section 5 of this 2008/490, we can write:

where:

• $\lambda_0 = -2 - 18x - 30x^2 - 36x^3$.
• $\lambda_1 = 1 - 12x - 18x^2 - 36x^3$.
• $\lambda_2 = 1 + 6x^2$.
• $\lambda_3 = 1$.

So we just need to compute:

and then multiply them all.

In what follows, remember that x = 4965661367192848881, which is a number of $63$ bits that can be expressed in the base $\{-1,0,1\}$ as follows:

1 - 2^4 + 2^9 + 2^11 + 2^16 + 2^19 + 2^21 + 2^22 + 2^25 + 2^27 + 2^30 + 2^34 + 2^36 + 2^37 + 2^39 + 2^41 + 2^44 + 2^47 + 2^48 + 2^51 - 2^53 + 2^56 + 2^58 + 2^62
[1,0,0,0,-1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,-1,0,0,1,0,1,0,0,0,1]
1000-1000010100001001011001010010001011010100100110010-1001010001

which has a Hamming weight of 24.

We prefer base $\{-1,0,1\}$ over base $\{0,1\}$ because x expressed in the latter is:

1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^8 + 2^11 + 2^16 + 2^19 + 2^21 + 2^22 + 2^25 + 2^27 + 2^30 + 2^34 + 2^36 + 2^37 + 2^39 + 2^41 + 2^44 + 2^47 + 2^48 + 2^51 + 2^53 + 2^54 + 2^55 + 2^58 + 2^62
[1,0,0,0,1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,1,1,0,0,1,0,0,0,1]
100011111001000010010110010100100010110101001001100101110010001

which has a Hamming weigth of 28.

We proceed as follows:

1. We start by computing $m^x, (m^x)^x, (m^{x^2})^x$.

2. Then, compute $m^p, m^{p^2}, m^{p^3}, (m^{x})^p, (m^{x^2})^p, (m^{x^3})^p, (m^{x^2})^{p^2}$ (use the Frobenius operator).

3. Next, we group the previous elements as follows:

   $$\begin{aligned} y_0 &= m^p \cdot m^{p^2} \cdot m^{p^3}, \\ y_1 &= \bar{m}, \\ y_2 &= m^{x^2p^2}, \\ y_3 &= \overline{m^{xp}}, \\ y_4 &= \overline{m^{x} \cdot m^{x^2p}}, \\ y_5 &= \overline{m^{x^2}}, \\ y_6 &= \overline{m^{x^3} \cdot m^{x^3p}}. \end{aligned}$$

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

4. Finally, compute the product:

   $$y_0 \cdot y_1^2 \cdot y_2^6 \cdot y_3^{12} \cdot y_4^{18} \cdot y_5^{30} \cdot y_6^{36}$$

$$
\begin{aligned}
&y_0 \cdot y_1^2 \cdot y_2^6 \cdot y_3^{12} \cdot y_4^{18} \cdot y_5^{30} \cdot y_6^{36} = \\ 
&(m^p \cdot m^{p^2} \cdot m^{p^3}) \cdot \left(\frac{1}{m}\right)^2 \cdot (m^{x^2p^2})^6 \cdot \left(\frac{1}{m^{xp}}\right)^{12} \cdot \left(\frac{1}{m^{x}m^{x^2p}}\right)^{18} \cdot \left(\frac{1}{m^{x^2}}\right)^{30} \cdot \left(\frac{1}{m^{x^3}m^{x^3p}}\right)^{36} \\
&= \underbrace{\left(\frac{1}{m}\right)^2 \cdot \left(\frac{1}{m^{x}}\right)^{18}\left(\frac{1}{m^{x^2}}\right)^{30}\left(\frac{1}{m^{x^3}}\right)^{36}}_{m^{\lambda_0}}\cdot \underbrace{m^p \cdot \left(\frac{1}{m^{xp}}\right)^{12} \cdot \left(\frac{1}{m^{x^2p}}\right)^{18} \cdot \left(\frac{1}{m^{x^3p}}\right)^{36}}_{m^{\lambda_1p}} \cdot \underbrace{m^{p^2} \cdot (m^{x^2p^2})^6}_{m^{\lambda_2p^2}} \cdot \underbrace{m^{p^3}}_{m^{\lambda_3p^3}} \\
&= m^{\lambda_0} \cdot m^{\lambda_1p} \cdot m^{\lambda_2p^2} \cdot m^{\lambda_3p^3} = m^{\lambda_0 + \lambda_1p + \lambda_2p^2 + \lambda_3p^3} = m^{\frac{p^4-p^2+1}{r}}
\end{aligned}
$$

To compute this product as efficient as possible, we use the vectorial addition chain technique as explained in the last part of Section 5 of [2008/490](https://eprint.iacr.org/2008/490.pdf):

which requires only $9$ multiplications and $4$ squarings.

Costs: $\underbrace{(63·3)S + (x·3)M}_{\text{Step 1}} + \underbrace{5 · (6\tilde{c} + 5\tilde{m}) + 2·(5\tilde{m})}_{\text{Step 2}} + \underbrace{4M + 5C}_{\text{Step 3}} + \underbrace{9M + 4S}_{\text{Step 4}}$

Frobenius Operator

As we have shown, in the final exponentation we must compute the first, second and third Frobenius operator $\pi_p,\pi_p^2,\pi_p^3$ 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) = O(254)$ $\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:

where $g = g_0 + g_1v + g_2v^2$ and $h = h_0 + h_1v + h_2v^2$ with $g,h \in \mathbb{F}_{p^{6}}$ and $g_i,h_i \in \mathbb{F}_{p^2}$.

Then, we have:

with $\gamma_{1,i} = (9+u)^{i\frac{p-1}{6}}$, $\gamma_{2,i} = (9+u)^{i\frac{p^2-1}{6}} = \gamma_{1,i} \cdot \bar{\gamma}_{1,i}$ and $\gamma_{3,i} = (9+u)^{i\frac{p^3-1}{6}} = \gamma_{1,i} \cdot \gamma_{2,i}$. Hence, assuming the precomputation of $\gamma_{1,i},\gamma_{2,i},\gamma_{3,i}$ for $i \in [5]$, we can compute $f^p,f^{p^2}$ or $f^{p^3}$ almost for free.

Costs: $\underbrace{6\tilde{c} + 5\tilde{m}}_{f^p}, \quad \underbrace{5\tilde{m}}_{f^{p^2}}, \quad \underbrace{6\tilde{c} + 5\tilde{m}}_{f^{p^3}}$

Speeding up Computations in the Cyclotomic Subgroup

I follow 2010/542 closely for this section.

Recall that:

and also:

For this optimitzation, we will further need the following $\mathbb{F}_{p^{12}}$ representation:

so that for $f = (g_0 + g_1 w^3) + (g_2 + g_3 w^3) w + (g_4 + g_5 w^3) w^2 \in C$, 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 \in B$.

This optimization is due to “compression” and “decompression” technique, which exploits the algebraic relationships arising from elements belonging to the cyclotomic subgroup $\mathbb{G}_{\phi_{6}(p^2)}$.

Compression and Decompression

If $f = g_0 + g_2w + g_4w^2 + g_1w^3 + g_3w^4 + g_5w^5$ then the compression function $\mathcal{C}$ is:

and the decompression function $\mathcal{D}$ is:

where:

Compressed Squaring

Now, on input $f \in \mathbb{G}_{\phi_{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_2w + h_4w^2 + h_1w^3 + h_3w^4 + h_5w^5$:

Exponentiation in the Cyclotomic Subgroup

Given $f \in \mathbb{G}_{\phi_{6}(p^2)} \subset \mathbb{F}_{p^{12}}^*$ and $e \geq 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_1e_0$ with $e_{\ell-1}=1$ and define $H_e = \{i : 1 \leq i \leq \ell - 1 \text{ and } e_i = 1\}$. Then:

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;

Appendix A: Field Isomorphisms

Recall that:

We use two additional representations of $\mathbb{F}_{p^{12}}$.

The first one is used to efficiently compute the Frobenius operator and is as follows:

The second one is used to speed up the squares and exponentations in the hard part of the final exponentiation:

Isomorphism between A and B

We start with $A = \mathbb{F}_{p^6}[w]/(w^2 - v)$ and $B = \mathbb{F}_{p^2}[w]/(w^6 - (9+u))$, where we notice that if we take $a = a_1 + a_2 \cdot w \in A$, we can use the identity $v = w^2$ to rewrite it as:

This relationship induces the following field isomorphism $\chi_{AB} : A \to B$ and its inverse $\chi_{AB}^{-1} : B \to A$: