1 Introduction

Pairing-based cryptography, as a member of elliptic curve cryptography (ECC), has utilized pairings to several notable applications beyond traditional and advanced cryptographic tools containing identity-based encryption [1, 2], aggregate signature [3, 4], functional encryption [5] and zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) [6, 7]. In addition, pairings can be used for public-key compression [8] and verifiable delay function construction [9] in isogeny-based cryptography. Most of these applications are built on the Tate pairing and its variants such as the Eta pairing [10], the Ate pairing [11, 12], the R-ate pairing [13] and the Optimal Ate pairing [14].

Efficient algorithms for pairing computations play an essential role in implementations of relevant protocols. There are two polynomial time algorithms for computing the Tate pairing and its variants. One is Miller’s algorithm [15] which was proposed in 1986. The other is Elliptic Net algorithm (ENA) which was proposed in 2007 by Stange [16]. Miller’s algorithm has been heavily optimized since 2000 and is now in a relatively mature phase. Many tricks have been employed to Miller’s algorithm for efficiency, such as twist maps and lazy reduction. Twist maps of elliptic curves allow us to transfer the operations of an extension field to its own proper subfield, which considerably reduces the number of multiplications. For a more in-depth description of twist maps, we refer to [11, 17]. Lazy reduction was first introduced in quadratic extension field arithmetic for Miller’s algorithm by Michael Scott [18] and further developed in [19]. It saves several modular reductions. Hence, it also brings significant improvements to Miller’s algorithm. Stange [16] first defined elliptic nets and gave a relationship between elliptic nets and the Tate pairing [1]. Elliptic nets are generalized from elliptic divisibility sequences [20]. These sequences arise from any choice of an elliptic curve and rational points on such a curve. For more information about elliptic divisibility sequences, see [21]. The method called Double-and-Add for updating each value of the block in the ENA was proposed by Shipsey [22]. One can compute pairings using elliptic nets of rank 2. The explicit formulas for computing some variants of the Tate pairing using the ENA were given in [23, 24]. In 2015, an improved version of the ENA (IENA) was proposed by Chen et al. [25]. They reduced the dimension of the block for pairing computations at the price of one inversion at the DoubleAdd step. Hence, the IENA can perform well if the parameter of the Miller loop has low Hamming weight. It should be noted that most popular pairing-friendly curves meet this condition. Due to the properties of the structure of elliptic nets, it is possible to design some parallel strategies for the ENA to compute pairings. Moreover, we can update all values of a block in each iteration of the ENA simultaneously if we change the dimension of the first vector of a block from eight to ten. More detailed information can be found in [26]. It is known that the (I)ENA as an alternative method to pairing computations is still more costly than Miller’s algorithm. Till now, there is a relative lack of research on the implementation of the (I)ENA.

Our Contributions. In this work, we aim to strengthen the (I)ENA as an easy-to-implement and efficient algorithm and to reduce the gap between the (I)ENA and Miller’s algorithm. Previous works on the (I)ENA preferred to implement this algorithm in Magma. Therefore, our work first implements the (I)ENA based on RELIC toolkit [27] in a combination of C and assembly language. Note that the base field arithmetic is implemented in the assembly language in the RELIC library. Our specific contributions are as follows.

  • We eliminate the inversion completely in the IENA. For the IENA, an inversion is always involved at the DoubleAdd step in the Double-and-Add algorithm. In this paper, we find that an inversion can be eliminated at the price of several multiplications in the IENA. The implementation indicates that the IENA works well when utilizing this trick.

  • We use the (I)ENA to compute the Optimal Ate pairing entirely on the twisted curve inspired by the previous work of Costello et al. [28], who explored the pairing computation entirely on the twisted curve via the process of Miller’s algorithm. In Miller’s algorithm, the pairing computation contains addition and doubling steps of the Miller loop. Since the procedure of the (I)ENA relies on the updating of the block and does not involve the evaluation of the line and vertical line at either addition or doubling step of the Miller loop, the use of the (I)ENA to compute the pairing on the twisted curve still requires a general proof. In this work, we present a new proof based on the theory of divisor to verify the relationship between the (Optimal) Ate pairing on an elliptic curve and its twisted curve. This proof relies only on the definition of the Tate pairing and the theory of divisors. Furthermore, we derive the explicit formulas of the line function of the Optimal Ate pairing on the twisted curve. In our implementations, we boost the performance of the (I)ENA on a 381-bit BLS12 curve at the 128-bit security level and a 676-bit KSS18 curve at the 192-bit security level by using twist maps, respectively [29].

  • We adopt lazy reduction [30] which only performs one reduction for the sum of several multiplications to the (I)ENA. In these algorithms, we observe that there are many terms of the form \(A \cdot B - C \cdot D\), where \(A,\,B,\,C,\,D\) belong to a finite field. This inspires us to apply lazy reduction for the (I)ENA. In our implementation, lazy reduction reduces by around 27% the number of modular reductions.

We conclude that pairings can be efficiently computed with the ENA. Our optimized implementation of the ENA with an execution time of \(2.16\,ms\) runs up to 4.9 times faster than the previous one on the 381-bit BLS12 curve on x64 platforms. Notice that Miller’s algorithm performs well in our implementation which takes about \(1.57\,ms\) on such a curve. Even though the ENA is still slower than Miller’s algorithm, the ratio between the cost of ENA and Miller’s algorithm is reduced from over 9 times to less than 2 times after the development of this work.

The rest of this paper is organized as follows. Section 2 gives an overview of pairings, twists of elliptic curves and the (I)ENA. In Sect. 3, we replace an inversion by several multiplications in the IENA. Section 4 analyzes the (Optimal) Ate pairing entirely on the twisted curve that is computed by the (I)ENA. In Sect. 5, we apply lazy reduction to the (I)ENA. The implementation and efficiency analysis are discussed in Sect. 6. Section 7 concludes the paper.

2 Preliminaries

In this section, we will give the definition of the Tate pairing and the (Optimal) Ate pairing. A brief description of twists of elliptic curves and the (I)ENA will also be provided.

2.1 Pairings

Let \({\mathbb {F}}_q\) be a finite field with the characteristic not equal to 2 or 3. Let \(E:y^2=x^3+Ax+B\) be a short Weierstrass curve over \({\mathbb {F}}_q\), where \(A,B \in {\mathbb {F}}_q\) and \(4A^3+27B^2 \ne 0\). We denote the q-power Frobenius endomorphism on E by \(\pi _q\). The order of \(E({\mathbb {F}}_q)\) is given by \(\#E(\mathbb F_q)=q+1-t\), where t is the Frobenius trace of \(\pi _q\). Choose a large prime r with \(r\mid \#E({\mathbb {F}}_q)\). Let \(k \in \mathbb {Z}\) be the embedding degree with respect to r, i.e., the minimal positive integer satisfying \(r\mid q^k-1\).

Choose \(P \in E({\mathbb {F}}_q)[r]\) and \(Q \in E({\mathbb {F}}_{q^k})[r]\). We denote by \(\mu _r\) the group of the rth roots of unity in \({\mathbb {F}}_{q^k}\). For an integer i and a point S on E, let \(f_{i,S}\) be a rational function such that

$$\begin{aligned} \textrm{Div}(f_{i,S})=i(S)-(iS)-(i-1)(\infty ). \end{aligned}$$

We also call the function \(f_{i,S}\) as the Miller function. Then the reduced Tate pairing [31] is defined as

$$\begin{aligned} \begin{aligned}&Tate:E({\mathbb {F}}_q)[r] \times E({\mathbb {F}}_{q^k}) \rightarrow \mu _r\\&\quad (P,Q)\mapsto Tate(P,Q)=f_{r,P}(Q)^{{q^k-1}/r}. \end{aligned} \end{aligned}$$

Furthermore, if we choose P and Q in specific subgroups of E[r], the pairing computation can be sped up. Define

$$\begin{aligned}{} & {} {\mathbb {G}}_1 \triangleq E[r]\bigcap Ker(\pi _q -[1]), \\{} & {} {\mathbb {G}}_2 \triangleq E[r]\bigcap Ker(\pi _q -[q]). \end{aligned}$$

Choose \(P\in {\mathbb {G}}_1\) and \(Q\in {\mathbb {G}}_2\), respectively. Let \(T=t-1\). We can define a pairing as follows.

$$\begin{aligned} \begin{aligned}&Ate_E:{\mathbb {G}}_2 \times {\mathbb {G}}_1 \rightarrow \mu _r\\&\quad (Q,P)\mapsto Ate_E(Q,P)=f_{T,Q}(P)^{{q^k-1}/r}, \end{aligned} \end{aligned}$$

which is called the Ate pairing [11].

The Ate pairing is the case of the Eta pairing [10] on ordinary elliptic curves. The length of the Miller loop of the Ate pairing is shorter than that of the Tate pairing [12, 13]. The Optimal Ate pairing allows us to obtain the shortest loop length [14, 32, 33]. Let \(l_{S,T}\) be the line through two points S and T. Let \(v_{T}\) be the vertical line passing through point T. The definition of the Optimal Ate pairing is given in the following theorem.

Theorem 1

[14, Theorem 4] Let \(\lambda =\alpha r = \sum _{i=0}^{\varphi (k)}c_iq^i\) with \(r \not \mid \alpha \), where \(\varphi (k)\) is the Euler function of k, then we can define a bilinear map

$$\begin{aligned} \begin{aligned}&Opt_E:{\mathbb {G}}_2 \times {\mathbb {G}}_1 \rightarrow \mu _r\\&\quad (Q,P)\mapsto Opt_E(Q,P)\\&\quad =\left( \prod _{i=0}^{\varphi (k)-1}f_{c_i,Q}^{q^i}(P)\cdot \!\!\!\prod _{i=0}^{\varphi (k)-1}\frac{l_{[s_{i+1}]Q,[c_iq^i]Q}(P)}{v_{[s_i]Q}(P)}\right) ^{{q^k-1}/r}, \end{aligned} \end{aligned}$$

where \(s_i=\sum _{j=i}^{\varphi (k)}c_jq^j\).

If \(\alpha k q^{k-1} \ne \left( \left( q^{k}-1\right) / r\right) \sum _{i=0}^{\varphi (k)-1} i c_{i} q^{i-1}\pmod r,\) then \(Opt_E\) is non-degenerate. We call \(Opt_E\) as the Optimal Ate pairing.

The implementation of the Tate pairing and its variants contains the Miller loop step and the final exponentiation step. At the Miller loop step, we first compute the value of the Miller function. We then raise this value to the power of \({(q^k-1)/r}\) at the final exponentiation step. For the computation of the Optimal Ate pairing, one should consider computing the value of line functions at the Miller loop step, which depends on the family of pairing-friendly curves. In this work, we mainly consider the implementation of the Optimal Ate pairing on the BLS12 and KSS18 curves. More specific information will be discussed in Sect. 6.

2.2 Twists of elliptic curves

In this subsection, we first recall the definition of twists of elliptic curves.

Definition 1

Let E be an elliptic curve over \({\mathbb {F}}_q\). An elliptic curve \(E'/{\mathbb {F}}_{q^{k/d}}\) is a twist of degree d of E if there exists an isomorphism \(\Psi _d:E'\rightarrow E\) defined over \({\mathbb {F}}_{q^k}\) and d is minimal.

The potential degree d of twists is 2, 3, 4 or 6 [1, 17]. For the BLS12 and KSS18 curves, the parameter \(A=0\) and the degree \(d=6\). In this case, the equation of the curve E is \(y^2=x^3+B\), and the curve \(E'\) is the sextic twist of E. The M-type and D-type twists are given below [34].

$$\begin{aligned} \begin{aligned}&M-type:\,E':y^{2}=x^{3}+B\xi \\&\quad \Psi _6: E'\rightarrow E \\&\quad (x, y) \mapsto \left( \xi ^{1/3} x, \xi ^{1 / 2} y\right) ,\\&D-type:\,E':y^{2}=x^{3}+ B/ \xi \\&\quad \Psi _6: E'\rightarrow E\\&\quad (x, y) \mapsto \left( \xi ^{-1/3} x, \xi ^{-1 / 2} y\right) . \end{aligned} \end{aligned}$$
(1)

Furthermore, we have the following theorem for the Tate pairing:

Theorem 2

[35, Chapter IX, Theorem 9] Let \(E_1/{\mathbb {F}}_q\) be an elliptic curve. Let \(r_0\) be a prime such that \(r_0\mid \#E_1({\mathbb {F}}_q)\). Suppose that the embedding degree with respect to q and \(r_0\) is k. Let \(\phi :E_1 \rightarrow E_2\) be an isogeny, where \(E_2\) is an elliptic curve over \({\mathbb {F}}_{q^k}\). Choose \(P \in E_1({\mathbb {F}}_q)[r_0]\) and \(Q \in E_2({\mathbb {F}}_{q^k})\). We have \(e(\phi (P),Q)=e(P,{\hat{\phi }}(Q))\), where \({\hat{\phi }}\) is the dual of \(\phi \).

Note that \(\Psi _d\) is an isogeny of degree 1. If we denote the dual of \(\Psi _d\) by \({\hat{\Psi }}_d\), then \({\hat{\Psi }}_d\circ \Psi _d =[1]\). Recall the definition of E in Sect. 2.1. Choose \(P \in E({\mathbb {F}}_q)[r]\) and \(Q' \in E'({\mathbb {F}}_{q^{k/d}})\). We can compute pairings \((Opt)Ate_{E'}({\hat{\Psi }}_d(P),Q')\) on the twisted curve \(E'\) whose Miller loop length is the same as the loop length of \((Opt)Ate_E(P,\Psi _d(Q'))\) on the original curve E.

Furthermore, define

$$\begin{aligned} \Phi _d=\Psi _d^{-1}\circ \pi _q \circ \Psi _d. \end{aligned}$$

One can verify that \(\Phi _d: E' \rightarrow E'\) is a homomorphism defined over \({\mathbb {F}}_{q^k}\) [36, 37], which can help us get some useful conclusions in Sect. 4.

2.3 The elliptic net algorithm

An elliptic net is a map W from a finitely generated free Abelian group G to an integral domain R, satisfying a certain recurrence relation as follows.

$$\begin{aligned} \begin{aligned}&W(\alpha +\beta +\delta )W(\alpha -\beta )W(\gamma +\delta )W(\gamma )\\&\qquad +W(\beta +\gamma +\delta )W(\beta -\gamma )W(\alpha +\delta )W(\alpha )\\&\qquad +W(\gamma +\alpha +\delta )W(\gamma -\alpha )W(\beta +\delta )W(\beta )\\&\quad =0, \end{aligned} \end{aligned}$$
(2)

where \(\alpha ,\,\,\beta ,\,\gamma ,\,\delta \in G\).

For each \(n \in {\mathbb {Z}}^{+}\), division polynomials \(\psi _n\in {\mathbb {Z}}[A,B,x,y]\) are defined as follows [17].

$$\begin{aligned} \begin{aligned}&\psi _0=0,\psi _1\!=\!1,\psi _2\!=\!2y,\\&\psi _3=3x^4\!+\!6Ax^2\!+\!12Bx\!-\!A^2,\\&\psi _4=4y(x^6\!\!+\!5Ax^4\!\!+\!20Bx^3\!\!-\!5A^2x^2\!\!-\!4ABx\\&\qquad \quad -\!8B^2\!\!-\!A^3),\\&\psi _{2n+1}\psi _1=\psi _{n+2}\psi _n^3\!-\!\psi _{n-1}\psi _{n+1}^3\,\,(n\ge 2),\\&\psi _{2n}\psi _2=\psi _n(\psi _{n+2}\psi _{n-1}^2\!-\!\psi _{n-2}\psi _{n+1}^2)\,\,(n \ge 3). \end{aligned} \end{aligned}$$

Division polynomials are examples of elliptic nets of rank 1, i.e., \(W(i)=\psi _i,\,\forall i \in {\mathbb {Z}}\). They can be used to compute scalar multiplication. Elliptic nets of rank 2 are applied for pairing computations. The relationship between the Tate pairing and an elliptic net is given below.

Theorem 3

[16, Theorem 6] Choose \(P\in E({\mathbb {F}}_q)[r]\) and \(Q \in E({\mathbb {F}}_{q^k})[r]\). Let \(\infty \) be the point in infinity. We denote the elliptic net associated with E, P, Q by \(W_{P,Q}\); then, we have

$$\begin{aligned} f_{r,P}(D_Q)=\frac{W_{P,Q}(r+1,1)W_{P,Q}(1,0)}{W_{P,Q}(r+1,0)W_{P,Q}(1,1)}, \end{aligned}$$

where \(D_Q=(Q)-(\infty )\).

One can compute the Tate pairing in polynomial time by using the ENA. For simplicity, we abbreviate \(W_{P,Q}(n,s)\) to W(n, s). Assume that \(W(1,0)=W(0,1)=1\). In [16], Stange defined a block that consists of a first vector of eight consecutive terms centered on the term W(i, 0) and a second vector of three consecutive terms centered on W(i, 1), where \(i \in {\mathbb {Z}}\). For the first vector, all of W(n, 0) terms can be updated by two formulas in Eqs. (3)-(4). By updating the first vector in the iteration, we can compute the scalar multiplication. For the second vector, we update the W(n, 1) terms by Eqs. (5)-(8). The updating process of a block V centered on i is shown in Figure 1.

$$\begin{aligned}{} & {} W(2i-1,0)=W(i+1,0)W(i-1,0)^3\nonumber \\{} & {} \qquad \qquad \qquad \qquad -W(i-2,0)W(i,0)^3, \end{aligned}$$
(3)
$$\begin{aligned}{} & {} W(2i,0)=(W(i,0)W(i+2,0)W(i-1,0)^2\nonumber \\{} & {} \qquad \qquad \qquad -W(i,0)W(i-2,0) \nonumber \\{} & {} \qquad \qquad \qquad W(i+1,0)^2)/W(2,0). \end{aligned}$$
(4)
$$\begin{aligned}{} & {} W(2i-1,1)=(W(i+1,1)W(i-1,1)W(i-1,0)^2\nonumber \\{} & {} \qquad \qquad \qquad \qquad -W(i,0)W(i-2,0)W(i,1)^2)/W(1,1),\nonumber \\ \end{aligned}$$
(5)
$$\begin{aligned}{} & {} W(2i,1)=(W(i-1,1)W(i+1,1)W(i,0)^2\nonumber \\{} & {} \qquad \qquad \qquad -W(i-1,0)W(i+1,0)W(i,1)^2), \end{aligned}$$
(6)
$$\begin{aligned}{} & {} W(2i+1,1)=(W(i-1,1)W(i+1,1)W(i+1,0)^2\nonumber \\{} & {} \qquad \qquad \qquad \qquad -W(i,0)W(i+2,0)W(i,1)^2)/W(-1,1),\nonumber \\ \end{aligned}$$
(7)
$$\begin{aligned}{} & {} W(2i+2,1)=(W(i+1,0)W(i+3,0)W(i,1)^2\nonumber \\{} & {} \qquad \qquad \qquad \qquad -W(i-1,1)W(i+1,1)\nonumber \\{} & {} \qquad \qquad \qquad \qquad W(i+2,0)^2)/W(2,-1). \end{aligned}$$
(8)
Fig. 1
figure 1

Updating process of a block centered on i

Full size image

In some certain conditions, the value W(2, 0) can be fixed to 1 by the equivalence of elliptic nets [38].

figure a

Generally, updating a block centered on i to a block centered on 2i is called the Double step, and updating a block centered on i to a block centered on \(2i+1\) is called the DoubleAdd step, which is represented by Double(V) and DoubleAdd(V), respectively. In [25], the authors improved the ENA by reducing the dimension of the first vector in an elliptic net from eight to seven. But we need to update the last term of the first vector at the DoubleAdd step by the following formula:

$$\begin{aligned} \begin{aligned}&W(2i+4,0)=(W(2i+3,0)W(2i+1,0)W(2,0)^{2}\\&\quad -W(3,0)W(1,0)W(2 i+2,0)^{2})/W(2 i, 0). \end{aligned} \end{aligned}$$
(9)

We show the IENA in Algorithm 1. The algorithm to compute the process of Lines 2-8 in Algorithm 1 is called the Double-and-Add algorithm. In fact, the overall process of the ENA is similar to that of the IENA. The main difference between the ENA and IENA is the saved term in the first vector, which affects the initial values of the block and the Double-and-Add algorithm.

3 Elimination of the inversion

In the IENA, an inversion is always involved at the DoubleAdd step. In this section, we will exploit the equivalence of the elliptic nets and perform local processing on the IENA to avoid the inversion in exchange for few multiplications.

When a block centered on i is updated to a block centered on \(2i+1\), we need to compute the inverse of W(2i, 0) for updating the value of \(W(2i+4,0)\) from Equation (9). To eliminate this inversion, we multiply \(W(\lambda ,0)_{2i-3\le \lambda \le 2i+4}\) by W(2i, 0) simultaneously at the DoubleAdd step. We have the following theorem to support this approach.

Theorem 4

Given a block V centered on i, i.e.,

$$\begin{aligned} W\!(\lambda ,\!0)_{i-\!3\le \lambda \le i+\!3} \text { and } W\!(\lambda ,\!1)_{i-\!1\le \lambda \le i+\!1} \!\in \! {\mathbb {F}}_{q^k}. \end{aligned}$$
  1. 1.

    If \(W\!(\lambda ,\!0)_{i-\!3\le \lambda \le i+\!3}\) are multiplied by \(\alpha \!\in \! {\mathbb {F}}_{q^k}^*\), i.e.,

    $$\begin{aligned} {\hat{W}}(\lambda ,0)_{i-3\le \lambda \le i+3}=\alpha \cdot W(\lambda ,0)_{i-3\le \lambda \le i+3}, \end{aligned}$$

    then at the DoubleAdd step, we will obtain the block centered on \(2i+1\), which is updated as follows.

    $$\begin{aligned} \begin{aligned}&{\hat{W}}(\lambda ,0)_{2i-2\le \lambda \le 2i+4}=\alpha ^4 \cdot W(\lambda ,0)_{2i-2\le \lambda \le 2i+4},\\&{\hat{W}}(\lambda ,1)_{2i\le \lambda \le 2i+2}=\alpha ^2 \cdot W(\lambda ,1)_{2i\le \lambda \le 2i+2}. \end{aligned} \end{aligned}$$

    Furthermore, if \(\alpha \ne 0\) is in a proper subfield of \({\mathbb {F}}_{q^k}\), then

    $$\begin{aligned} \left( \frac{{\hat{W}}_{P,Q}(s,1)}{\hat{W}_{P,Q}(s,0)}\right) ^{\frac{q^k-1}{r}}=\left( \frac{ W_{P,Q}(s,1)}{ W_{P,Q}(s,0)}\right) ^{\frac{q^k-1}{r}}, \end{aligned}$$
    (10)

    where s is an integer.

  2. 2.

    If \(W\!(\lambda ,\!0)_{i-3\le \!\lambda \!\le i+3}\) and \(W\!(\lambda ,\!1)_{i-1 \le \!\lambda \!\le i+1}\) are multiplied by \(\alpha \!\in \!{\mathbb {F}}_{q^k}^*\), then at the DoubleAdd step, all the values of the block will be multiplied by \(\alpha ^4\!\), and Equation (10) still holds.

Proof

Recall the recursive formula for \(W(2i-1,0)\) and W(2i, 0) in Equations (3)-(4). We multiply \(W(\lambda ,0)_{i-3\le \lambda \le i+3}\) by \(\alpha \); then, we have

$$\begin{aligned} \begin{aligned} \hat{W}(2i-1, 0)&=\alpha ^4( W(i + 1, 0)W(i - 1, 0)^3 \\&- W (i - 2, 0)W (i,0)^3)\\&\!=\!\alpha ^4\cdot W\!(2i-1,0).\\ \hat{W}(2i,0)&=\alpha ^4\cdot W(2i,0). \end{aligned} \end{aligned}$$
(11)

Therefore,

$$\begin{aligned} {\hat{W}}(\lambda ,0)_{2i-2\le \lambda \le 2i+3}=\alpha ^4 \cdot W(\lambda ,0)_{2i-2\le \lambda \le 2i+3}. \end{aligned}$$

For the term \(W(2i+4,0)\),

$$\begin{aligned} \begin{aligned}&\hat{W}(2i+4, 0) =\alpha ^8( W(2i + 3, 0)W(2i + 1, 0)W(2,0)^2) \\&\quad - \alpha ^8(W (3, 0)W (1,0)W(2i+2,0)^2)/\alpha ^4W(2i,0)\\&\quad =\alpha ^4W(2i+4,0). \end{aligned} \end{aligned}$$

This finishes the proof for the first assertion.

Now we consider the second vector in the block. Note that there are only two values of the first vector involved for computing each \(W(\lambda ,1)_{2i\le \lambda \le 2i+2}\). The new updated \(\hat{W}(\lambda ,1)_{2i\le \lambda \le 2i}\) will be multiplied by \(\alpha ^2\).

Next, we will verify Equation (10). For any integer s,

$$\begin{aligned} \begin{aligned} \hat{W}_{P,Q}(s,0)&=\alpha ^{2l}\cdot {W}_{P,Q}(s,0),\\ \hat{W}_{P,Q}(s,1)&=\alpha ^l\cdot {W}_{P,Q}(s,1), \end{aligned} \end{aligned}$$

where \(l\in {\mathbb {Z}}\). If the constant \(\alpha \) is chosen to be in a proper subfield of \({\mathbb {F}}_{q^k}\), then \(\alpha ^{\frac{q^k-1}{r}}\) is equal to 1. This verifies Equation (10).

If \(W\!(\lambda ,\!0)_{i-3\le \!\lambda \!\le i+3}\) and \(W\!(\lambda ,\!1)_{i-1 \le \!\lambda \!\le i+1}\) are multiplied by \(\alpha \) simultaneously, then from Case 1, we have

$$\begin{aligned} {\hat{W}}(\lambda ,0)_{2i-2\le \lambda \le 2i+4}=\alpha ^4W(\lambda ,0)_{2i-2\le \lambda \le 2i+4}. \end{aligned}$$

As for the second vector of the block, since each \(W(\lambda ,1)_{i-1 \le \!\lambda \!\le i+1}\) is multiplied by \(\alpha \), \(W(\lambda ,1)_{2i\le \lambda \le 2i+2}\) will be multiplied by \(\alpha ^4\) according to Equations (6)-(8). It is clearly seen that Equation (10) still holds, because

$$\begin{aligned} \frac{\hat{W}_{P,Q}(s,1)}{\hat{W}_{P,Q}(s,0)}=\frac{\alpha ^l{W}_{P,Q}(s,1)}{\alpha ^l{W}_{P,Q}(s,0)}=\frac{{W}_{P,Q}(s,1)}{{W}_{P,Q}(s,0)}, \end{aligned}$$

for some integer l.

So far the proof has been finished. \(\square \)

Fig. 2
figure 2

Updating a block centered on i at the DoubleAdd step

Full size image

Remark 1

The process of Case 1 in Theorem 4 is shown in Figure 2. Theorem 4 considers the situation at the DoubleAdd step. Indeed, we have a similar result at the Double step. It can be proved in the same manner. Theorem 4 can also be extended for any pairing-friendly curves. However, if we need to guarantee that Equation (10) holds for any \(\alpha \in {\mathbb {F}}_{{q}^{k}}^*\), we should multiply every term in the block by \(\alpha \).

For some popular pairing-friendly curves, we will have a friendly situation. Taking the BLS12 curve, we choose in this work as an example; there is a proposition which is available for the (I)ENA. The related parameters of the BLS12 curve can be seen in Sect. 6.1 and the towering scheme of the extension field is shown as follows.

  • \({\mathbb {F}}_{q^2}={\mathbb {F}}_q[u]/\langle u^2-\beta \rangle \), where \(\beta = -1\);

  • \({\mathbb {F}}_{q^6}={\mathbb {F}}_{q^2}[v]/\langle v^3-\xi \rangle \), where \(\xi = u+1\);

  • \({\mathbb {F}}_{q^{12}}={\mathbb {F}}_{q^6}[\omega ]/\langle \omega ^2-v \rangle \).

Recall the definition of \(\Psi _{6}\) in Sect. 2.2. The corresponding M-type twist \(\Psi _6\) is

$$\begin{aligned} \begin{aligned}&\Psi _6: E'\rightarrow E \\&\quad (x, y) \mapsto \left( \xi ^{1/3} x, \xi ^{1 / 2} y\right) .\\ \end{aligned} \end{aligned}$$
(12)

From the towering scheme of \({\mathbb {F}}_{q^{12}}\), we know \(\omega ^2=v\) and \(v^2=\xi \). Hence, we have \(\xi ^{1/3}=v\), \(\xi ^{1/2}=v\omega \).

Proposition 5

Choose \(P \in E({\mathbb {F}}_q)\) and \(Q'=(x_{Q'},y_{Q'})\in E'({\mathbb {F}}_{q^2})\). Define \(Q\triangleq \Psi _6(Q')\).

Write \(W_{\!Q,P}(s,\!0)=a_0+a_1\varvec{\omega }\), where \(s\!\in \! {\mathbb {Z}},a_0,a_1\in {\mathbb {F}}_{q^6}\). Then we have

$$\begin{aligned} W_{\!Q,P}(s,\!0)= \left\{ \begin{aligned}&a_0, \quad \text {s is odd}\\&a_1\varvec{\omega },\quad \text {s is even} \end{aligned} \right. . \end{aligned}$$

Proof

We abbreviate \(W_{Q,P}(s,0)\) to \(W_{Q}(s,0)\) for convenience. Note that \(W(s,\!0)\!=\!\psi _s\!\in \!{\mathbb {Z}}[x,y,A,B]\), where \(\psi _s\) is a division polynomial. Therefore, we just prove the proposition in two situations according to [39, Section 3.2].

  1. 1.

    Assume that s is odd. Then \(\psi _s\) is a polynomial in \({\mathbb {Z}}[x,y^2,A,B]\). For the short Weierstrass elliptic curve \(y^2=x^3+Ax+B\), we can replace \(y^2\) by a polynomial in x. Hence, if we evaluate \(\psi _s\) at the point Q, then the x-coordinate of Q is \(x_{Q'}\varvec{v} \in {\mathbb {F}}_{q^6}\). Hence, \(W_{Q}(s,0)\) will be always in a proper subfield of \({\mathbb {F}}_{q^{12}}\), i.e., \(W_{Q}(s,0)=a_0\).

  2. 2.

    If s is even, then \(\psi _s\) is a polynomial in \(2y{\mathbb {Z}}[x,y^2,A,B]\). Evaluating \(\psi _s\) at Q, we find that the y-coordinate of Q is \(y_{Q'}\varvec{v\omega } \!\in \!{\mathbb {F}}_{q^{12}}\). According to Case 1, the evaluation of a polynomial in \({\mathbb {Z}}[x,y^2,A,B]\) at Q will be in \({\mathbb {F}}_{q^6}\). Combined with the y-coordinate of Q, we have \(a_0\) is equal to 0. Therefore, \(W_{Q}(s,0)=a_1\varvec{\omega }\).

So far the proposition has been proved. \(\square \)

In order to eliminate the inverse of W(2i, 0) in Equation (9), we multiply \(W(\lambda ,\!0)_{2i-\!2 \le \lambda \le 2i+\!4}\) by W(2i, 0) at the DoubleAdd step. It follows from Proposition 5 that the term W(2i, 0) can be written as \(a_1\varvec{\omega }\) on the BLS12 curve, where \(a_1\in {\mathbb {F}}_{q^6}\). Recall the towering scheme of \({\mathbb {F}}_{q^{12}}\). We have \(\omega ^2=v\) and \(v\in {\mathbb {F}}_{{q}^6}\). Then both \(W(2i,0)^2=a_1^2\varvec{\omega ^2}=a_1^2\varvec{v}\) and \(W(2i,0)^4=a_1^4\varvec{v}^2\) will always be in \({\mathbb {F}}_{q^6}\). Hence, \(W(2i,0)^2\) and \(W(2i,0)^4\) are equal to 1 if we raise them to the power of \(\frac{q^k-1}{r}\). As long as we do not meet the inversion in the last iteration, Equation (10) will always be true. Then we can use the new block to compute pairings by using the IENA. Fortunately, the last iteration of the Miller loop on the BLS12 and KSS18 curves always invoke the Double step. This means that we can use 5 multiplications instead of 1 inversion.

4 The elliptic net algorithm on the twisted curve

The application of the twists maps has brought significant improvements in Miller’s algorithm. When we use the (I)ENA to compute the (Optimal) Ate pairing, the algorithm will also have a good improvement if all the related parameters are on the twisted curve. In 2010, Costello et al. [28] proposed the Ate pairing entirely on the twisted curve. The authors considered the line and vertical line on twisted curves at addition and doubling steps of the Miller loop and proved the correctness of this case via the procedure of Miller’s algorithm. It seems to be natural that the (I)ENA should also be able to compute pairings entirely on the twisted curve. However, in the (I)ENA, we only need to update the values of the block and use these values to compute the value of the Tate pairing and its variants in the end. The proof of Costello et al. [28] is not suitable for the case of the (I)ENA. In the following, we will present a new proof that verifies the relationship between the (Optimal) Ate pairing on the elliptic curve and its corresponding twisted curve based on the divisor theory.

Recall the definition of the elliptic curve E in Sect. 2.1. Let \(E'/{\mathbb {F}}_{q^{e}}\) be the twist of E of degree d with \(e=k/d\). Let \(\pi '_{q^e}\) be the \(q^e\)-power Frobenius map on \(E'\). There exists an isomorphism \(\Psi _d:E'\rightarrow E\) over \({\mathbb {F}}_{q^k}\). Then we can define two subgroups

$$\begin{aligned} \begin{aligned} {\mathbb {G}}_1'&\triangleq E'[r]\bigcap Ker(\pi ' _{q^e} -[1]),\\ {\mathbb {G}}_2'&\triangleq E'[r]\bigcap Ker(\pi ' _{q^e} -[q^{e}]). \end{aligned} \end{aligned}$$

Actually, the parameter of the Miller loop length T can be set as \((t-1)\,mod\,r\) [12]. Firstly, we give a new derivation of the theorem about the Ate pairing entirely on the twisted curve as follows.

Theorem 6

For \(P' \triangleq \Psi _d^{-1}(P) \in {\mathbb {G}}_2'\) and \(Q' \in {\mathbb {G}}_1'\), we can define a pairing on \({\mathbb {G}}_1' \times {\mathbb {G}}_2'\) if \(r^2\not \mid T^k-1\):

$$\begin{aligned} \begin{aligned}&Ate_{E'}\!:\!{\mathbb {G}}_1' \!\times \!{\mathbb {G}}_2' \!\rightarrow \!\mu _r\\&\quad (Q',P')\!\mapsto \! Ate_{E'}(Q',P')\\&\quad =\left( f_{T,Q'}\left( P'\right) \right) ^{{q^k\!-\!1}/r}. \end{aligned} \end{aligned}$$

Proof

We only need to prove \(f_{T\!,\Psi _d(Q'\!)}\!=\!f_{T\!,Q'}\!\circ \!\Psi _d^{-1}\), for all \(Q'\in {\mathbb {G}}_1'\). The divisor of \(f_{T,\Psi _d(Q')}\) is

$$\begin{aligned} \textrm{Div}(f_{T,\Psi _d(Q')})\!=\!T(\Psi _d(Q'))-([T]\Psi _d(Q'))-(T-1)(\infty ). \end{aligned}$$

Since \(\Psi _d\) is an isomorphism, we get

$$\begin{aligned} \begin{aligned} (\Psi _d)^*\textrm{Div}(f_{T,\Psi _d(Q')})&=T(Q')-([T]Q')-(T-1)(\infty ),\\&=(f_{T,Q'}). \end{aligned} \end{aligned}$$

Furthermore, we have

$$\begin{aligned} (\Psi _d)^*\textrm{Div}(f_{T,\Psi _d(Q')})=\textrm{Div}(f_{T,\Psi _d(Q')}\circ \Psi _d). \end{aligned}$$

Thus, we can deduce that \(f_{T,\Psi _d(Q')} \circ \Psi _d=f_{T,Q'}\). Composing the formula with \(\Psi _d^{-1}\) on both sides, we get

$$\begin{aligned} f_{T,\Psi _d(Q')}(P)=\left( f_{T,Q'}\circ \Psi _d^{-1}\right) (P). \end{aligned}$$

This completes the proof of the theorem. \(\square \)

Remark 2

In Miller’s algorithm, when we compute the Ate pairing on the original curve with twists, the field arithmetic is in the field where \(Q'\) is located. Since the cost of the transformations involved in each iteration is very small, the final value we require can be easily obtained by twist maps. In detail, we only need to multiply the value by a fixed value \(\alpha \) in \({\mathbb {F}}_{q^k}\). This multiplication is sparse in general. But for the (I)ENA, if we adopt the same idea to use twist maps, the value will be multiplied by a different value of \(\alpha \) in each iteration, which means that the transformation is not a friendly process. Therefore, we consider computing the Ate pairing on the twisted curve for the (I)ENA.

4.1 The optimal ate pairing on the twisted curve

For the situation of the Optimal Ate pairing entirely on the twisted curve, we can present the following theorem.

Theorem 7

Let \(\lambda \!=\! mr\) with \(r\!\not \mid \! m\) and \(\lambda \!=\! \sum _{i=0}^{\varphi (k)}c_iq^i\).

Define

$$\begin{aligned} \Phi _{d,i}\!=\!\Psi _d^{-1}\circ [c_iq^i]\circ \Psi _d, \end{aligned}$$

where \(\Phi _{d,s_i}\!=\!\Psi _d^{-1}\circ [s_i]\circ \Psi _d\) and \(s_i\!=\!\sum _{j=i}^{\varphi (k)}c_jq^j\). There exists a pairing on \(\mathbb {G'}_1 \times \mathbb {G'}_2\):

$$\begin{aligned} \begin{aligned}&Opt_{E'}:{\mathbb {G}}'_2 \times {\mathbb {G}}'_1 \rightarrow \mu _r\\&\quad (Q'\!,\!P')\!\mapsto Opt_{E'}(Q'\!,\!P')\\&\quad =\left( \prod _{i=0}^{\varphi (k)}\!\!f_{c_i,Q'}^{q^i}\!\left( P'\right) \cdot \!\!\!\prod _{i=0}^{\varphi (k)-1}\!\!\frac{l_{\Phi _{d,s_{i+1}} \!,\Phi _{d,i}(\!Q'\!)}}{v_{\Phi _{d,s_i} \!(\!Q'\!)}}(P')\!\right) ^{\frac{q^k\!-1}{r}}. \end{aligned} \end{aligned}$$

Proof

It follows from Theorem 6 that

$$\begin{aligned} \textrm{Div}(\prod _{i=0}^{\varphi (k)}f_{c_i,Q'}^{q^i}\circ \Psi _d^{-1})=\textrm{Div}(\prod _{i=0}^{\varphi (k)}f_{c_i,\Psi _d(Q')}). \end{aligned}$$

Let \(Q_i\triangleq [s_{i+1}]\circ \Psi _d(Q')\). Consider the relation between \(l_{\Phi _{d,s_{i+1}} ,\Phi _{d,i}(Q')}\) and \(l_{Q_i,[c_iq^i]\Psi _d(Q')}\). Then we have the following divisor of the line function:

$$\begin{aligned} \begin{aligned} \textrm{Div}(l_{Q_i,[c_iq^i]\Psi _d(Q')})&=(Q_i)+([c_iq^i]\Psi _d(Q'))\\&\quad +(-Q_{i+1})-3(\infty ). \end{aligned} \end{aligned}$$

Since \(\Psi _d\) is an isomorphism,

$$\begin{aligned} \begin{aligned} (\Psi _d)^*\textrm{Div}(l_{Q_i,[c_iq^i]\Psi _d(Q'\!)}\!)&=(\Psi _d^{-1}\!(Q_i)\!)\!+\!(\!-Q_{i+1}\!)\!-\!3(\!\infty \!)\\&\quad +(\Psi _d^{-1}\circ [c_iq^i]\circ \Psi _d(Q'))\\&=(l_{\Phi _{d,s_{i+1}} ,\Phi _{d,i}(Q')}).\\ \end{aligned} \end{aligned}$$

Therefore,

$$\begin{aligned} l_{Q_i,[c_iq^i]\Psi _d(Q')}(P)=l_{\Phi _{d,s_{i+1}} ,\Phi _{d,i}(Q')}\circ \Psi _d^{-1}(P). \end{aligned}$$

Similarly,

$$\begin{aligned} v_{Q_i}(P)=v_{\Phi _{d,i}}(Q')\circ \Psi _d^{-1}(P). \end{aligned}$$

This completes the proof of the theorem. \(\square \)

Remark 3

We have \(\pi _q\circ \Psi _d(Q')=[q]\Psi _{d}(Q')\), for each \(\Psi _{d}(Q')\in {\mathbb {G}}_2\). Since \(\pi _q\) is an endomorphism and \(\Psi _d\) is an isomorphism over \({\mathbb {F}}_{q^k}\), we have

$$\begin{aligned} \pi _q\circ \Psi _d(Q')=\Psi _{d}\circ [q](Q'). \end{aligned}$$

Therefore,

$$\begin{aligned} \Psi _d^{-1}\circ \pi _q\circ \Psi _{d}(Q')=[q](Q'), i.e., \Phi _{d,1}(Q')=[q](Q'). \end{aligned}$$

It is known that a point in \({\mathbb {G}}_1'\) can be mapped to a point in E[r]. This also means that the points on the line function on the twisted curve can be obtained via Remark 3.

Note that the ratio between the inversion and multiplication costs over \({\mathbb {F}}_{q^k}\) decreases as the embedding degree k becomes larger. It follows that the cost of 1 inversion may be close to that of 5 multiplications. However, when we compute the (Optimal) Ate pairing entirely on the twisted curve, each term of the first vector in the block centered on i will be in \({\mathbb {F}}_{q^e}\). Hence, it is necessary for this situation to eliminate the inversion at the DoubleAdd step.

5 The elliptic net algorithm with lazy reduction

Lazy reduction can also be employed to speed up the (I)ENA. It can save the number of modular reductions during the calculation. The main idea of lazy reduction is to put the required modular reductions for the sum of several multiplications like \(\sum a_ib_i\) over \({\mathbb {F}}_q\) to the end. Therefore, these multiplications only need 1 modular reduction over \({\mathbb {F}}_q\). In this paper, we use Montgomery reduction [40], so the cost of a modular reduction is equal to the cost of one multiplication without reduction.

When we use the (I)ENA to compute the (Optimal) Ate pairing, lots of multiplications of the form \(A \cdot B \pm C \cdot D\) are contained, which needs 2 modular reductions normally. But lazy reduction allows us to use one modular reduction only. It should be noted that we are not concerned about violating the upper bound of Montgomery reduction for this situation since one only uses lazy reduction once each time with \(A,B,C,D\in {\mathbb {F}}_q\). We mainly improve the term W(3, 0) and W(4, 0) at the initialization step. The number of modular reductions of three situations is given in Table 1.

Table 1 Number of Modular Reductions at the Initialization Step
Full size table

The explicit updating formulas at the Double-and-Add step are mentioned in Sect. 2.3. The Double(V) and DoubleAdd(V) functions are combined with lazy reduction, and we adopt the new Double-and-Add algorithm in [25], requiring 10 terms in total. We present the optimized Double-and-Add algorithm based on the IENA in  Appendix A. Assume that our terms in the block are all in the finite field \({\mathbb {F}}_q\). At Lines 7-17 we compute the Double(V) function. We update 7 terms in the first vector and 3 terms in the second vector that are both centered on 2i in a block. In the ENA, we need 42 modular reductions in each iteration. The number of modular reductions decreases to 37 in the IENA. With the help of lazy reduction, the updating process for each term can save one modular reduction, so 10 terms will save 10 modular reductions in total. The DoubleAdd(V) function is computed at Lines 9-33. These steps contain 40 modular reductions in the IENA originally, and the number of modular reductions is reduced to 30 in each iteration with lazy reduction. Table 2 shows the number of modular reductions among the ENA, IENA, and our optimized algorithm at the Double-and-Add step, respectively.

Table 2 Number of Modular Reductions at the Double-and-Add Step
Full size table

6 Implementation and analysis

In this section, we implement the optimization of the (I)ENA for the pairing computation. Note that we mainly consider the improvement of the computation at the Miller loop. Our implementations are performed on an Intel Core i7-8550U CPU processor operating at 1.80 GHz with hyperthreading turned off and TurboBoost disabled. We compile the benchmarks on GCC 7.4.0 with the -O2 flag set and test them on a 64-bit Linux platform, running Ubuntu 18.04 LTS. Our code is based on version 0.5.0 of the RELIC toolkit [27], and we adopt the finite field arithmetic implemented in the RELIC library which needs the GMP library for both curves. Hence, our benchmarks use the assembly language to improve the performance of our implementations. Our code is available at https://github.com/wennycai/ENA.

We will use different methods to test the efficiency of computing the Optimal Ate pairing on the pairing-friendly curves at the 128-bit security level and 192-bit security level, respectively. Notice that the DoubleAdd(V) function is not friendly in the IENA. In general, we choose the Miller loop parameter which has a low Hamming weight so that we can use Double(V) function more frequently in the whole iterations to accelerate the IENA. The pairing-friendly curves we choose are the 381-bit BLS12 and 676-bit KSS18 curves. We also implement Miller’s algorithm for benchmarks. The version of Miller’s algorithm we use in our work is the fastest one implemented by Aranha et al. in the RELIC library. For fair comparison, we use the same algorithms for the finite field arithmetic and the final exponentiation in the RELIC library when we implement the ENA, IENA and Miller’s algorithm. The recent work of [41] proposed some more efficient field arithmetic algorithms to speed up the computation of the Optimal Ate pairing on the 381-BLS12 curve which obtained a 1.37\(\times \) speedup on an x64 Intel processor. Our implementations can also benefit from their improvement. The authors plan to open-source the optimized implementation of pairing computations on the 381-bit BLS12 curve that was integrated to the state-of-the-art pairing library RELIC 0.5.0. We specify some symbols here to show the amount of operations in this section:

  • \(M_{k}\): Multiplication over \({\mathbb {F}}_{q^{k}}\), \(S_{k}\): Squaring over \({\mathbb {F}}_{q^{k}}\),

  • M: Multiplication over \({\mathbb {F}}_{q}\), S: Squaring over \({\mathbb {F}}_{q}\),

  • \(I_k\): Inversion over \({\mathbb {F}}_{q^{k}}\), A: Addition over \({\mathbb {F}}_{q}\).

6.1 381-bit BLS12 curve

The concrete parameters for the 381-bit BLS12 curve with embedding degree \(k=12\) are given as follows.

  • \(z=-2^{63} - 2^{62} - 2^{60} - 2^{57} - 2^{48} - 2^{16}\);

  • \(r = z^4- z^2 + 1\);

  • \(q = (z-1)^2(z^4-z^2+1)/3+z\);

  • \(E:y^2=x^3+4\) over \({\mathbb {F}}_q\);

  • \({\mathbb {F}}_{q^2}={\mathbb {F}}_q[u]/\langle u^2-\beta \rangle \), where \(\beta = -1\);

  • \({\mathbb {F}}_{q^6}={\mathbb {F}}_{q^2}[v]/\langle v^3-\xi \rangle \), where \(\xi = u+1\);

  • \({\mathbb {F}}_{q^{12}}={\mathbb {F}}_{q^6}[\omega ]/\langle \omega ^2-v \rangle \);

  • Twisted curve \(E'\) : \(y^2=x^3+4\xi \) over \({\mathbb {F}}_{q^2}\).

Recall that \(P\in E({\mathbb {F}}_q)\) and \(Q'\in E'({\mathbb {F}}_{q^{e}})\). Note that we do not need to compute the evaluation of the line function on the BLS12 curve. Hence, we only compute the following formula:

$$\begin{aligned} \left( f_{z,\Psi _6(Q')}(P)\right) ^{\frac{q^{12}-1}{r}}\,\, or \,\, \left( f_{z,Q'}(\Psi _6^{-1}(P))\right) ^{\frac{q^{12}-1}{r}}. \end{aligned}$$

The amount of operations for \(f_{z,\Psi _6(Q')}\) and \(f_{z,Q'}\) in one iteration is \(7S_{12}+\frac{67}{2}M_{12}\) and \(6S_2+62M_2+S_{12}+\frac{3}{2}M_{12}\) at the Double step in the ENA, respectively. In our implementation, we use the ratios \(1I_{12}\approx 3M_{12}\), \(1I_2\approx 13M_2\), \(1M_2\approx 3M\) and \(1M_{12}\approx 54M\) [19]. In the IENA, we need \(6S_{12}+31M_{12}+I_{12}\) without twists at the DoubleAdd step. If we compute pairings on the twisted curve, the operations can be reduced to \(1S_{12}+1M_{12}+5S_2+39M_2+1I_2\). Without considering the influence of delay error, it is necessary to eliminate the inversion if we compute the Optimal Ate pairing on the twisted curve. Because the cost of 1 inversion is greater than that of 5 multiplications in \({\mathbb {F}}_{q^2}\). Moreover, we choose to compute \(f_{-z,Q'}\) and use the relationship

$$\begin{aligned} (f_{z,Q'})^{(q^{12}-1)/r}=(\dfrac{1}{f_{-z,Q'}})^{(q^{12}-1)/r} \end{aligned}$$

to revise the value, since z is a negative number. In order to make the IENA work well, we expand \(-z\) in the non-adjacent form (NAF) to reduce the proportion of nonzero digits. Although the ENA is much slower than Miller’s algorithm, it still counts in milliseconds. We cycle the benchmarks 10, 000 times and take the average value to ensure the stability and accuracy of our results. The comparison about the efficiency of different methods is provided in Table 3.

Table 3 Efficiency Comparison for pairing computations on a 381-bit BLS12 Curve
Full size table
Table 4 Efficiency Comparison for pairing computations on a 676-bit KSS18 Curve
Full size table

Table 3 shows that this work speeds up the ENA indeed. Twist maps have a good performance for the (I)ENA. The application of twist maps improves the efficiency of the ENA and IENA by \(80.8\%\) and \(79.8\%\), respectively. In addition, lazy reduction further accelerates the (I)ENA and brings around \(9\%\) efficiency improvement on the twisted BLS12 curve. It should be noted that on the BLS12 curves, the cost of 1 inversion over \({\mathbb {F}}_{q^{12}}\) is close to that of 5 multiplications over \({\mathbb {F}}_{q^{12}}\). Hence, we only need to avoid the inversion on the twisted BLS12 curve, which makes the IENA be up to \(3.66\%\) faster than before.

6.2 676-bit KSS18 curve

Now we give the parameters of the 676-bit KSS18 curve with embedding degree \(k=18\) below:

  • \(z=-2^{85}-2^{31}-2^{26}+2^6\);

  • \(r = (z^6+37z^3+343)/343\);

  • \(q = (z^8+5z^7+7z^6+37z^5+188z^4+259z^3+343z^2+1763z+2401)/21\);

  • \(E:y^2=x^3+2\) over \({\mathbb {F}}_q\);

  • \({\mathbb {F}}_{q^3}={\mathbb {F}}_q[u]/\langle u^3-\beta \rangle \), where \(\beta = -2\);

  • \({\mathbb {F}}_{q^6}={\mathbb {F}}_{q^2}[v]/\langle v^2-\xi \rangle \), where \(\xi = u\);

  • \({\mathbb {F}}_{q^{18}}={\mathbb {F}}_{q^6}[\omega ]/\langle \omega ^3-v \rangle \);

  • Twisted curve \(E'\) : \(y^2=x^3+2/\xi \) over \({\mathbb {F}}_{q^2}\).

We need to calculate

$$\begin{aligned} \left( \!f_{z,\Psi _6(Q')}\cdot f_{3,\Psi _6(Q')}^q\cdot l_{[z]\Psi _6(Q'),[3q]\Psi _6(Q')}\!(P)\!\!\right) ^{\frac{q^{18}-1}{r}} \end{aligned}$$

or

$$\begin{aligned} \left( \!f_{z,Q'}\!\!\cdot \! \!f_{3,Q'}^q\!\!\cdot \!\! l_{\Psi _6^{-1}\!\circ \! [z]\!\circ \! \Psi _6(Q'),\Psi _6^{-1}\!\circ \! [3q]\!\circ \! \Psi _6(Q')}\!(\Psi _6^{-1}\!(P)\!)\!\!\right) ^{\frac{q^{18}\!-1}{r}} \end{aligned}$$

for computing the Optimal Ate pairing on this curve. Notice that the Optimal Ate pairing on the 676-bit KSS18 curve can achieve the 192-bit security level. Therefore, we just cycle the benchmark 1, 000 times and take the average value as the final result. Table 4 shows the timings of different methods for computing the Optimal Ate pairing.

Similar to the results on the BLS12 curve, the computation of the Optimal Ate pairing using the (I)ENA on twisted KSS18 curve can be significantly sped up compared with the computation on the KSS18 curve, which is \(70\%\) and \(66.83\%\) faster, respectively. As for the performance of lazy reduction, we find that the application of this technique saves more operations on the KSS18 curve than that on the BLS12 curve. This is mainly due to the fact that the embedding degree of the KSS18 curve is larger than that of the BLS12 curve. Moreover, there are more iterations of the Miller loop on the KSS18 curve than on the BLS12 curve. Since the runtime of the ENA on KSS18 curve is 68.54ms, the effect of 2ms saved by lazy reduction is not obvious here. Considering the IENA on the twisted KSS18 curve, the elimination of the inversion can save about 385, 000 clock cycles compared to the original one, and the lazy reduction can save about 1.4 million clock cycles.

According to our results, the efficiency of computing the Optimal Ate pairing on the twisted curve is much higher than that on the original curve for the (I)ENA. In addition, we can further improve the efficiency of the algorithm by eliminating the inversion in the IENA. However, the gap between the optimized IENA and Miller’s algorithm on the KSS18 curve is larger than that on the BLS12 curve. This is related to the extension field arithmetic. For example, we require \(6M+3M_3+6S_3+1S_{18}\) and one sparse multiplication over \({\mathbb {F}}_{q^{18}}\) at the Double step in Miller’s algorithm [19]. But we require \(1S_{18}+9M_{18}+5S_3+22M_3\) at the Double step in this work.

7 Conclusions

In this work, we improved the Elliptic Net algorithm. For the original Elliptic Net algorithm, we analyzed its efficiency and presented implementations on the computation of the Optimal Ate pairing on a 381-bit BLS12 curve and a 676-bit KSS18 curve with several tricks, respectively. In particular, lazy reduction was able to reduce by around \(27\%\) of the required modular reductions. Moreover, the application of twist maps helped us reduce the number of multiplications and the improvement was significant. Besides, the improved Elliptic Net algorithm was also further developed by eliminating the inversion in exchange for few multiplications. On the 381-bit BLS12 curve, this work improved the performance of the Optimal Ate pairing by \(80\%\) compared with the original version on a 64-bit Linux platform. The implementation on the 676-bit KSS18 curve had shown that this work was \(71.5\%\) faster than the previous ones. Although the Elliptic Net algorithm was still slower than Miller’s algorithm, it can compute pairings efficiently on personal computers.