Efficient Software Implementation of GMT6-672 and GMT8-542 Pairing-Friendly Curves for a 128-Bit Security Level

Abstract

A Bilinear pairing on an elliptic curve defined over a finite field provides an attractive prospect for designing cryptographic schemes with various functionalities. An elliptic curve over which a computationally efficient bilinear pairing can be defined is called a “pairing-friendly curve”. Finding families of pairing-friendly curves with sufficient anticipated bit security has attracted significant research attention. For example, the Barreto-Neahrig (BN) and Barreto-Lynn-Scott (BLS) curves, are existing curves of this type. However, there is a need for alternatives to back up these already evaluated curves. In 2020 Guillevic, Masson, and Thomé (GMT) proposed pairing-friendly curves with embedding degrees 5 to 8 range. GMTk denotes curves with an embedding degree k. A composite k is preferred from the efficiency viewpoint. However, to the best of the GMT6 and GMT8 curves have been reported in the literature. In this paper, novel field-towering methods using two types of extension method and constructions are developed. These methods are applied to efficiently implement and analyze the bilinear pairings based on the GMT6 curve over a 672-bit prime field and the GMT8 curve over a 542-bit prime field. The pairing-computation times of our developed software evaluated using an Intel Core i7-8700 (@4.3 GHz Turbo Boost on) is computer are 0.987 ms and 1.12 ms for GMT6-672 and GMT8-542, respectively indicating the practicality of these curves.

1 Introduction

A Bilinear pairing (hereafter simply “pairing”) over an elliptic curve is valuable for implementing advanced cryptography, such as aggregate signatures [1], homomorphic encryption [2], etc. One of the recent innovative protocols based on pairing is the zero-knowledge succinct noninteractive argument of knowledge (zk-SNARKs) [3]. Pairing is a nondegenerate bilinear map obtained from the direct product of two additive groups $\mathbb {G}_1$ and $\mathbb {G}_2$, resulting in a multiplicative group $\mathbb {G}_3$. The groups $\mathbb {G}_1$ and $\mathbb {G}_2$ are generally subgroups obtained from elliptic curve groups $E(\mathbb {F}_p)$ and $E(\mathbb {F}_{p^k})$, where E, p, and k denote an elliptic curve, field characteristic, and embedding degree, respectively. Pairings constructed over elliptic curves require different properties and security levels depending on the particular application. Therefore, the investigation of new curves of efficient pairing computation (called “pairing-friendly” curves) constitutes a significant research area. The Barreto-Naehrig (BN) curves [5], Barreto-Lynn-Scott curves (BLS) [6], and Kachisa-Schaefer-Scott (KSS) curves are the most well-known families of pairing-friendly curves, which have been widely studied as efficient candidates for 128-bit level security pairings. Besides, there is an attack reported in [7] improves the number field sieve algorithm in discrete-logarithm problems in extension fields and affects the security level of many pairing-friendly curves. Hence, the parameters of pairing-friendly curves are forced to be replaced with their parameters for 128-bit security levels with enough margin. This parameter replacement has been studied only for a short period since the year 2016, after it the performance and security assessment for the well-known curves appear vague. In 2020, Guillevic, Masson, and Thomé (GMT) [8] proposed new curves generated by a modified Cocks-Pinch method. These curves satisfy the 128-bit level security against the attack mentioned in [7]. We refer to the paper [8] as “the GMT paper”. Moreover, we denote the curves with $k = 6, 8$ proposed in [8] as the GMT6 and GMT8 curves, respectively. The GMT paper presented algorithms for fast pairing calculation. A simple model estimates the computational timings of pairing computation over the GMT6 and GMT8, where both results are 1.5 ms using an Intel Core i7-8700@3.2 GHz computer. Although the results reported in the GMT paper are promising, to the best of our knowledge, there is no study on rigorous software implementation for these curves. For this purpose, this paper aims to provide the first and efficient software implementation of the GMT curves with a detailed cost analysis.

Our Contributions. The following three main contributions are present in this paper. First, two types of efficient field towering methods for the GMT6 and GMT8 curves with the type-I all-one polynomial field (AOPF) [11] and the optimal extension field (OEF) [12] are proposed. These fields are used as the first subextension fields for fast paring calculation. Furthermore, the number of arithmetic operations of the proposed extension field towering is investigated and a new GMT8 curve parameter optimized for our extension fields is provided. Second, an unique detailed cost at the algorithm level is provided for implementing Miller’s algorithm [4] with twists [13], and the required cost is reevaluated using an accurate expression. Moreover, the polynomials suggested by the GMT paper are reviewed for calculating the fast final exponentiation calculation and revised for efficiently calculating the orders of both curves. Finally, the experimental results obtained from the implemented software regarding the pairings over the GMT6 and GMT8 curves based on the proposed constructions are presented. The software implementations, which are based on the crypto library [14] and the GNU MP library (GMP) version 6.2.1, give rise to pairing computation of the GMT6 and GMT8 curves in 0.987 ms and 1.12 ms, respectively, using an i7-8700 (@4.3 GHz Turbo Boost enabled) computer without using the lazy reduction technique.

Related Research Works. Lavice et al. [9] proposed a small-area pairing-computation architecture using the FPGA for the updated 128-bit level pairing-friendly curves. They also proposed an attractive formula for calculating the squaring in the quadratic cyclotomic subgroup. We adopt this suggested squaring method employed in the quadratic cyclotomic subgroup and use it in our proposed tower of extension fields to reduce the calculation cost.

Notation. In this paper, a multiplication, squaring, and inversion cost in $\mathbb {F}_{p^k}$ is denoted as $m_k$, $s_k$, and $i_k$, respectively. The symbol $a_k$ denotes an addition cost in $\mathbb {F}_{p^k}$, where it is assumed that subtraction, left-shift, and right-shift costs in $\mathbb {F}_{p^k}$ are identical to $a_k$. m is used with $m_1$, and $s_1$ summarizes the total cost of $m_1 + s_1$ in $\mathbb {F}_p$. To distinguish parameters with different characteristics with the same embedding degree, each curve parameter is given a different designation using a bit length of characteristic p as the suffix, such as the GMT8-544 and GMT8-542.

2 Preliminaries

The GMT curves with embedding degrees $k=6, 8$ and ate pairing over the GMT curves are reviewed in this section.

2.1 Guillevic-Masson-Thomé (GMT) Curves with Embedding Degrees 6 and 8

Guillevic, Masson, and Thomé [8] proposed pairing-friendly elliptic curves based on the Cocks-Pinch algorithm with embedding degrees $k=5,6,7,8$. The curves with even embedding degrees $k=6$ and 8 (GMT6 and GMT8) are capable of calculating pairing efficiently. The parameters of the GMT curves (field characteristic p(u), order r(u), and Frobenius trace t(u) with coefficient ${h_t}, {h_y}$) are given by the following polynomials, where the integer parameters $u, h_y, h_t \in \mathbb {Z}$ are selected as p and r are prime numbers. The complex multiplication (CM) discriminant of the GMT6 curve is $D=3$ with elliptic curve $E:y^2= x^3 + b$ where $x,y \in \mathbb {F}_{p^6}$ with non-zero coefficient $b \in \mathbb {F}_{p}$. The $\rho$-value$= log(p)/log(r)$ of GMT6 is 2.63. For GMT8 curve, the CM discriminant is $D=4$ with the elliptic curve $E:y^2= x^3 + ax$ where $x,y \in \mathbb {F}_{p^8}$ with the nonzero coefficient $a \in \mathbb {F}_{p}$. For $k=8$, the obtained GMT8-542 curve has a slightly better $\rho$-value$= 2.12$ than the GMT6 curve.

The number of rational points on the elliptic curve E over the finite field $\mathbb {F}_p$ is expressed as $\#E(\mathbb {F}_p) = p + 1 - t$ according to the Hasse’s theorem. The elliptic curve E also forms an additive group in the extension field $E(\mathbb {F}_{p^k})$, where k is the embedding degree of the curve. The order of $E(\mathbb {F}_{p^k})$ is $\#E(\mathbb {F}_{p^k}) = p^k + 1 - t_k$, where $t_k = \alpha ^k + \beta ^k$ and $\alpha$ and $\beta$ are complex conjugate numbers. The r-torsion subgroup of E, which is defined as $E[r] := \{P | P \in E, [r]P = \mathcal {O}\}$ has two unique subgroups of order r. These subgroups are useful for efficient pairing computation. Let the $\pi _p$ be Frobenius endomorphism and the first subgroup $\mathbb {G}_1 = E[r]\cap \text {ker}(\pi _p-[1]) \subset E(\mathbb {F}_p)[r]$, which is defined over $\mathbb {F}_p$. The second subgroup $\mathbb {G}_2 = E[r]\cap \text {ker}(\pi _p-[p]) \subset E(\mathbb {F}_{p^k})[r]$, which is defined over $\mathbb {F}_{p^k}$. The subgroup order r satisfies the condition $r|(p^k-1$), $r|\#E(\mathbb {F}_{p})$, $r^2|\#E(\mathbb {F}_{p^k})$ which are important for pairing computation optimization.

2.2 Ate Pairing over the GMT6 and GMT8 Curves

Let $\mathbb {G}_3$ be a multiplicative subgroup defined as

$$\begin{aligned} \mathbb {G}_3 = \mathbb {F}_{p^k}[r] \end{aligned}$$

(1)

where k is the embedding degree of the pairing-friendly curve. For three Abelian groups $\mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_3$, an ate pairing $a_T$ can be defined as follows:

$$\begin{aligned} a_T: \mathbb {G}_2 \times \mathbb {G}_1&\rightarrow \mathbb {G}_3, \end{aligned}$$

(2)

$$\begin{aligned} (Q, P)&\mapsto (f_{T,Q}(P))^{(p^k-1)/r} \end{aligned}$$

(3)

where $T = u - 1$ and $f_{T,Q}$ is a rational function with a divisor $\text {div}(f_{T,Q}) = T(Q) - ([T]Q) - (T-1)(\mathcal {O})$. Ate pairing for the GMT6 and GMT8 curves is calculated by using Algorithm 1.

In Algorithm 1, the calculation steps 1 to 10 are identified as Miller’s algorithm, where steps 2 to 10 are particularly called Miller’s loop. Steps 3, 6 and 9 describe the calculations of the rational functions $l_{R,R}, l_{R,Q}$ together with the elliptic curve doubling (ECD) and elliptic curve addition (ECA) calculations. We call the calculations of $l_{R,R}$ together with the ECD as DBLLine. Similarly, we call the calculations of and $l_{R,Q}$ together with the ECA as ADDLine. UPDATE1 and UPDATE2 are “sparse” multiplications in $\mathbb {F}_{p^k}$ with less computational load than the standard multiplication in $\mathbb {F}_{p^k}$.

The input $T = u - 1$ is expressed in a nonadjacent form (NAF), which represents integers in certain conditions as three value types of 1, 0, $-1$, rather than a binary form for efficient pairing calculating. Miller’s algorithm is also known as an algorithm capable of using a 2-NAF since the inversion operation $l_{R,-Q}(P)$ can be easily calculated in this case.

Step 11 is known as the final exponentiation, the details of the final exponentiation calculation for the GMT6 and GMT8 curves are described in Sect. 5.2.

2.3 Ate Pairings over GMT Curves with Twists

The GMT6 curve with the CM discriminant $D=3$ and input $Q \in \mathbb {G}_2$ used for ate paring over the elliptic curve $E: y^2= x^3 + b$ known as having an isomorphism $\psi$. The isomorphism $\psi$ projects the subgroup $\mathbb {G}_2 \subset E(\mathbb {F}_{p^6})$ to a same order subgroup $\mathbb {G'}_2 \subset E'(\mathbb {F}_p)$ where the sextic twist $E': y^2 = x^3 +b/z, z \in \mathbb {F}_p$. Since two subgroups have the same information, the required cost heavy arithmetics in $\mathbb {F}_{p^6}$ can be replaced by the simple calculations in $\mathbb {F}_{p}$. The isomorphism $\psi$ from the twisted curve to the original curve can be defined as follows:

$$\begin{aligned} \psi : E'&\rightarrow E, \end{aligned}$$

(4)

$$\begin{aligned} Q'(x, y)&\mapsto Q(xz^{-1/3},yz^{-1/2}) \end{aligned}$$

(5)

With assuming that both $P \in \mathbb {G}_1 \subset E(\mathbb {F}_p)$ and $Q \in \mathbb {G'}_2 \subset E'(\mathbb {F}_p)$, the twisted ate pairing for the GMT6 curve can be computed as follows:

$$\begin{aligned} a_T: \mathbb {G'}_2 \times \mathbb {G}_1&\rightarrow \mathbb {G}_3, \end{aligned}$$

(6)

$$\begin{aligned} (Q', P)&\mapsto (f_{T,\psi (Q')}(P))^{(p^6 - 1)/r} \end{aligned}$$

(7)

In this case, the ADDLine and DBLLine can be computed in $\mathbb {F}_p$.

The GMT8 curve $E: y^2 = x^3 + ax$ with a CM discriminant $D=4$ has a different type of twist called “quartic twist”. The map $\varphi$ from the twisted elliptic curve $E'$ to the original curve E is defined as follows:

$$\begin{aligned} \varphi : E'&\rightarrow E,\end{aligned}$$

(8)

$$\begin{aligned} Q'(x, y)&\mapsto Q(xz^{-1/2},yz^{-3/4}) \end{aligned}$$

(9)

where $z \in \mathbb {F}_{p^2}$ is a quadratic non-residue in $\mathbb {F}_{p}$, $x^4 - z \in \mathbb {F}_{p^2}[x]$ is irreducible, the twisted curve $E': y^2 = x^3 +ax/z$, and $Q' \in \mathbb {G'}_2 \subset E'(\mathbb {F}_{p^2})$. Similar to the GMT6 curve, ate pairing with the quartic twist for the GMT8 curve can be computed as follows:

$$\begin{aligned} a_T: \mathbb {G'}_2 \times \mathbb {G}_1&\rightarrow \mathbb {G}_3, \end{aligned}$$

(10)

$$\begin{aligned} (Q', P)&\mapsto (f_{T,\varphi (Q')}(P))^{(p^8-1)/r} \end{aligned}$$

(11)

In this case, the GMT8 curves with embedding degree 8 can compute the ADDLine and DBLLine functions of ate pairing in $\mathbb {F}_{p^2}$ arithmetics. Even though the twist maps reduce the number of arithmetic operations in the pairing, the total cost of Miller’s algorithm depends on other elements, such as the Miller’s loop parameter T and the coordinate system. Furthermore, optimizing the final exponentiation calculation and not only Miller’s algorithm (for example, factorizing the polynomial $(p^k-1)/r$ $(k=6, 8)$ and performing fast squaring in the extension fields), is also a key component for fast pairing computations.

3 Review of Extension Field Classes

For fast pairing computation, the efficiency of the multiplication over the extension fields heavily decides it’s efficiency. To construct an extension field, first the primitive root c of f(x) is preferred to choose from the twist curve parameter z [13]. Second, the primitive root of f(x) is preferred to be as simple as possible (for example $c=2$). These constraints make impose a difficulty to find efficient irreducible polynomials for pairing. A tower of extension fields that have nested structures is proposed based on [10]. In this section, the existing classes of practical extension fields are initially reviewed and then the candidates for the tower of fields available for the GMT curves are indicated.

3.1 Optimal Extension Fields

Bailey and Paar [12] introduced the following formal definition for constructing extension fields consisting of a polynomial basis:

Definition 1 (Optimal extension fields, OEFs)

OEFs are the extension fields satisfying the following three properties.

• 1. Characteristic: A pseudo-Mersenne prime number p of the form $p = 2^l \pm c$, where $l,c \in \mathbb {Z}$.

• 2. Modular Polynomial: An irreducible binomial $x^m-s$, where $s \in \mathbb {F}_p$ and m is the extension degree.

• 3. Basis: A set $\{1,\omega ,\omega ^2,...,\omega ^{m-1}\}$, where $\omega$ is a primitive root of the modular polynomial.

Although the characteristic p is a pseudo-Mersenne prime number in the OEF definition, it is known that an OEF is actually capable of general prime numbers. An OEF has several fast multiplication algorithms for different degrees m, such as Karatsuba method [19], the Karatsuba-like method [20], and Toom-Cook method [21]. Specifically $m = 2$ and $s = -1$ constitute the most important variant, where the squaring computation in $\mathbb {F}_{p^2}$ requires only two multiplications in $\mathbb {F}_{p}$, using the Karatsuba method. We call this technique “Karatsuba complex method,” which is a famous and standard technique for accelerating pairing calculation.

3.2 All-One Polynomial Extension Fields

Unlike an extension field such as the polynomial based OEF described above, a special extension with a Gaussian normal basis was introduced by Nogami et al. [11]. This field is called all-one polynomial field (AOPF). Later Nekado et al. extended its definition and classified several types of AOPFs, such as type-I X [18] and type-II X [15, 17]. The definition of Type-I AOPF is given as follows:

Definition 2 (Type-I All-one polynominal Fields)

Type-I AOPFs are the extension fields satisfying the following three properties.

• 1. Characteristic: A pseudo-Mersenne prime number p of the form $p = 2^l \pm c$, where $l,c \in \mathbb {Z}$.

• 2. Modular Polynomial: An all-one irreducible polynomial $(x^{m+1}-1)/(x-1)$, where $s \in \mathbb {F}_p$ and $m+1$ is a prime number.

• 3. Basis: A pseudo basis $\{\omega ,\omega ^2,,\omega ^3...,\omega ^{m}\}$ is equivalent to the normal basis

  $\{\omega , \omega ^p, \omega ^{p^2},...,\omega ^{p^{m-1}}\}$ where $\omega$ is a primitive root of the modular polynomial.

Although the characteristic p is a pseudo-Mersenne prime number in the Definition 2, it is known that an AOPF is actually capable of general prime numbers. An efficient way to calculate the multiplication in an AOPF is to use the cyclic vector multiplication algorithm (CVMA), which is more efficient than the multiplication in an OEF. According to Nekado et al. [18], the squaring in the quadratic type-I AOPF: $\mathbb {F}_{p^2} = \mathbb {F}_p[\omega ] / (\omega ^2 + \omega +1)$ only requires two multiplications in $\mathbb {F}_p$ as follows:

$$\begin{aligned}&\alpha = (a_0, a_1),\ \alpha ^2 = \beta =(b_0, b_1), \end{aligned}$$

(12)

$$\begin{aligned}&b_0 =\{ -a_1(a_0 - a_1)+a_0\},\ b_1 = \{-a_0(a_0-a_1)-a_1\} \end{aligned}$$

(13)

where $\alpha , \beta \in \mathbb {F}_{p^2}$ and $a_0, a_1, b_0, b_1 \in \mathbb {F}_p$. Unlike the OEF, the type-I AOPF has much constraints. For example, $m+1$ must be a prime number, which restricts the degree of AOPF extension to an even number only. Furthermore, since the degree of type-II AOPF, the squaring in $\mathbb {F}_{p^2}$ requires three multiplications in $\mathbb {F}_p$, which is less efficient compared with the type-I AOPF or the adapted $z=s=-1$ OEF in Karatsuba complex method. In addition, if the probability of a general prime number to construct a degree-2 type-I AOPF is at most 50%. Still, the 2 ${\textbf {m}}$ cost squaring, the quadratic extension field of both OEF with $s=-1$ and type-I AOPF are still good candidates for a fast pairing calculation.

4 Proposal of Efficient GMT6 and GMT8 Curve Parameters and Their Field-Towering Schemes

As described in Sect. 3, building an efficient tower of an extension field with twist capability has a few constraints regarding the selection of the polynomial primitive root. Although the field towering system reduces the degree of irreducible polynomials to be explored, finding the curve parameters with an efficient computation cost is still complicated. In this section, the parameter selection for both GMT6 and GMT8 curves is described, and new curve parameters and tower construction methods for efficient pairing computation over GMT curves are proposed.

4.1 GMT6 Curve Parameters and Towers

The GMT paper [8] suggests the use of parameters for the GMT6 curve, as shown in Table 1. These parameters are denoted as GMT6-672. The GMT paper suggests the direct sextic extension using the irreducible polynomial $x^6-s, s=2 \in \mathbb {F}_p$ for the pairing computation over GMT6-672. Since 2 is a quadratic non-residue (QNR) and a cubic non-residue (CNR) in $\mathbb {F}_p$, the twist parameter z can be equivalent to $z = 2$. In this work, a field towering scheme $\tau _1$ based on the extension proposed in the GMT paper was derived, as shown in Table 3. However, we found that the suggested $\tau _1$ cost 2 extra addition in $\mathbb {F}_{p^2}$ squaring compare to $z=s=-1$; therefore, the arithmetic costs in $\tau _1$ is not the best for pairing calculation.

We propose a new variant of field towering scheme $\tau _2$ for efficient pairing computation over the GMT6 curve using both the sextic twist and Karatsuba complex techniques. $-1$ is not CNR in $\mathbb {F}_p$. Therefore, we had to find an alternative, QNR and CNR elements in $\mathbb {F}_p$ for the twist parameter z without changing the entire tower construction. Using numerical experiments, we found that the element $-4 \in \mathbb {F}_p$ satisfies the requirements. The cost estimations presented in Table 3 show that the extension field construction $\tau _2$ exhibits less $\mathbb {F}_p$ addition costs in $\mathbb {F}_{p^6}$ than $\tau _1$.

4.2 GMT8 Curve Parameters and Towers

The GMT8-544 curve proposed in [8] with the extension Field $\mathbb {F}_{p^8} = \mathbb {F}_{p}[x]/(x^8 - 5)$ which only capable with OEF and Type-II AOPF. We present an alternative characteristic p for the GMT8 curve with both OEF and Type-I AOPF construction available which can achieve flexible and efficient implementation. To find such a characteristic, we focus on finding a prime number available with either the Karatsuba complex or type-I AOPF. According to the GMT paper [24], the 2-NAF weight of some parameters is required for efficient computation over the GMT8-544 curves as follows:

$$\begin{aligned} u:\text {2-naf weight} \le 5, h_y:\ \text {2-naf weight} \le 7, h_t:\ \text {2-naf weight} \le 4 \end{aligned}$$

(14)

In the GMT paper, the evaluated security level of the proposed GMT8-544 curve is 131-bits. We investigated for new parameters which satisfies approximately the 128-bit security level by focusing the characteristic search in the 525 - 544 bit range. Looking for only the characteristic satisfying the condition above for quadratic type-I AOPF and OEF construction could be obtained. The parameters found are denoted as GMT8-542; these are presented in Table 2. The subgroup security and twist subgroup security of our GMT8-542 are the same with original GMT8-544; $\mathbb {G}_1, \mathbb {G}_2$ subgroup-security are confirmed, the twist-subgroup is not secure.

Compared to the original GMT8-544 curve, $h_y$ in the proposed curve has 2 more weights in the 2-NAF. A part from this disadvantage, the proposed GMT8-542 parameters are available only with the type-I AOPF, and 1/3 cost reduction is achieved for the squaring operation in the extension fields. Based on the extension proposed in the GMT paper, we derived a field-towering scheme $\tau _3$ as shown in Table 3. In this case, the element 3 is a QNR in $\mathbb {F}_p$, and the square root of 3 in $\mathbb {F}_{p^2}$ is also a QNR element which makes the quartic twist available for this tower.

We propose a more efficient towering scheme $\tau _4$, where the first subextension field $\mathbb {F}_{p^2}$ is constructed using the type-I AOPF method. A simple QNR element $(1,-1) \in \mathbb {F}_{p^2}$ for the second and third stage OEFs is selected. Since $(1,-1)$ is QNR, the quartic twist is also available in $\tau _4$. Two towers of extension fields and their arithmetic costs for each curve are summarized in Table 3. The newly proposed towers $\tau _2 \text { and } \tau _4$ exhibit less number of arithmetic operations for the squaring and the cyclotomic subgroup squaring in $\mathbb {F}_{p^2}$, $\mathbb {F}_{p^6}$, and $\mathbb {F}_{p^8}$.

Table 1. GMT6-672 parameters [8]

Table 2. GMT8-542 parameters

The final exponentiation raising power of $(p^k-1)/r$ is heavily dependent on the squaring cost in $\mathbb {F}_{p^k}$. We can use two strategies to accelerate the final exponentiation: compressed squaring introduced by Karabina [25] and cyclotomic subgroup squaring [9, 26]. Both algorithms are efficient compared with the regular squaring in the extension fields; however, the compressed squaring requires inversion operation in $\mathbb {F}_p$, which could be the bottleneck of pairing computation.

In Table 3, the $s_k^{cyclo}$ is represented by the square in the cyclotomic subgroup of extension field $\mathbb {F}_{p^k}$. $s_k^{cyclo}$ represents the cost of the cyclotomic subgroups squaring in $\mathbb {F}_{p^k}$. The cyclotomic subgroup squaring equation for $\tau _1$ and $\tau _2$ was adopted from [26, Sect. 3.2]. For $\tau _3$, we adopt the cyclotomic subgroup squaring equation from [26, Sect. 3] was adopted, whereas for $\tau _4$, the equation from a recent work [9] was selected to prevent the multiplication with $(\omega ^2 + \omega )^{-1}$ in the $\mathbb {F}_{p^4}$ multiplication.

5 Implementation of Ate Pairing over the GMT6 and GMT8 Curves

In this section, the details of the proposed pairing implementation are presented. Among the proposed towers of the extension fields, $\tau _2$ and $\tau _4$ are the best constructions for the GMT6 and GMT8 curves, respectively. This section provides a detailed calculation of pairing cost based on these towers.

Table 3. Arithmetic calculation costs in the tower of the extension fields

5.1 Implementation of Miller’s Algorithm

In previous studies, many sophisticated techniques were proposed to improve the performance of Miller’s algorithm. For example, the optimal coordinate system depends on the type of the underlying elliptic curves. Base on the GMT paper [8, Table 5], the homogeneous projective coordinate system (weight[1:1])) for the GMT6-672 curve was adopted. This system was proposed by Costello et al. in [23] and later modified in [22, Section 5].

For the proposed GMT8-542 curve, the Miller’s algorithm with the projective coordinate system (weight[1:2]) was adopted. This is also suggested by Costello et al. in [22, Sect. 4]. As a Miller’s loop parameter, the GMT6-672 has 129-bit $T=u-1$ with a 2-NAF weight of 2, whereas the GMT8-542 curve has a 65-bit $T=u-1$ with a 2-NAF weight $= 4$. The cost of the implemented functions in Miller’s loop based on the $\tau _2$ and $\tau _4$ field-towering schemes is summarized in Table 4.

Table 4. Cost of miller’s loop in $\tau _2$ and $\tau _4$

In Table 4, the column “Call” indicates the number of function calls per Miller’s algorithm execution. Since DBLLine does not require UPDATE1 in the first loop of Miller’s algorithm, UPDATE1 has one less call than DBLLine. Two ADDLine functions are denoted “ADDLine” and “ADDLine$'$” in Table 4. Due to $3 i_1$ and $1 m_1$ precomputation, ADDLine in Miller’s loop can be replaced with “ADDLine$'$”. Although the pairings and applications employ “ADDLine$'$”, the only functional with constant P, Q is the subgroup generator of $\mathbb {G}_1$ and $\mathbb {G}'_2$. Thus, pairings without restricting any of the application functionalities were implemented.

5.2 Implementation of Final Exponentiation

In the second part of pairing calculation, the result of Miller’s algorithm is raised to the power of ${(p^k-1)}/{r}$. This is also known as final exponentiation ${(p^k-1)}/{r}$ can be separated into two parts; the easy part and the hard part. The complexity of the final exponentiation largely depends on the curve parameters, especially the polynomials of characteristic p(u), order r(u), and Frobenius trace t(u). Using the following equation, the GMT curves feature a very unique and efficient construction [8]:

$$\begin{aligned} t' \equiv u^i + 1\ \equiv p + 1 \text { (mod }r), (i=1) \end{aligned}$$

(15)

$$\begin{aligned} j = \frac{p+1-t'}{r}, \end{aligned}$$

(16)

GMT6-672 Final Exponentiation

As mentioned above, the final exponentiation can be separated into two parts such as follows:

$$\begin{aligned} \frac{p^6-1}{r}= (p^3-1)(p+1)\times \frac{(p^2-p+1)}{r} \end{aligned}$$

(17)

The easy part $(p^3-1)(p+1)$ requires two Frobenius endomorphism calculations $f_6$ for p and $p^3$. The Frobenius endomorphism for the raised power of $p^{k}/2$ does not require any multiplication when k is even. Moreover, as shown in Table 3, the OEF nested tower of the extension field only requires 4 m for the Frobenius endomorphism $f_k$.

For the hard part, using the replacement technique given in (17) and (18) where $c=j$ (where $\varPhi _6(x)$ is the 6-th cyclotomic polynomial), $\frac{(p^2-p+1)}{r}$ can be broken down to:

$$\begin{aligned} \frac{\varPhi _6(t'-1)}{r} + {(p+t'-2)}c = 1 +(p+t'-2)c \end{aligned}$$

(18)

The hard part can be multiplied by a small integer, which does not change the bilinear pairing integrity. In this case, a multiplication by 3 is recommended, so that the polynomial 3c does not have any fraction terms, such as

$$\begin{aligned} 3(1 +(p+t'-2)c) = 3 + 3c(p+u-1) \end{aligned}$$

(19)

However, bilinearity could not be achieved using (19) with the polynomial 3c provided in Sect. 5.2 (3) of the GMT paper. Thus, our version of 3c was recalculated and corrected as follows:

$$\begin{aligned} 3c = ((1+3w+9w^2)(u-1)+(6w+9w^2))(u-1)+9w+9w^2, \end{aligned}$$

(20)

where $w = h_y/2$. We propose an efficient calculation order for 3c, which is shown in Table 5. However, we realize Nanjo et al. [16] already proposed the same equation in their paper’s TABLE IX. The final exponentiation costs using the above 3c calculation based on $\tau _2$ are summarized in Table 7. Compare with the original GMT672 final exponentiation hard part, our calculation order reduced $4m_6$ and $s_6$.

Table 5. Calculation of the raised power of GMT6-672 hard part-3c

GMT8-542 Final Exponentiation

Similar to the GMT6-672 curve, the power of the GMT8-542 final exponentiation can also be divided into two parts as follows:

$$\begin{aligned} \frac{p^8-1}{r}= (p^4-1)\times \frac{(p^4+1)}{r} \end{aligned}$$

(21)

In this case the easy part $(p^4-1)$ only requires 1 $m_6$ and 1 $i_6$. Using again the replacement technique given in (17) and (18) with parameter $u' = u -1$. The hard part of GMT8-542 can be broken down as follows:

$$\begin{aligned} \frac{(p^4+1)}{r} = \frac{\varPhi _8(t'-1)}{r} + d(p+t'-1)(p+(t'-1)^2) = 1 + d(p+u)(p^2+u^2) \end{aligned}$$

(22)

According to the GMT paper, thr hard part of embedding degree 8 is multiplied by 4 as follows:

$$\begin{aligned} 4 + 4d(p+u)(p^2+u^2) \end{aligned}$$

(23)

Similar to the GMT6-672, 4d was recalculated and corrected as follows:

$$\begin{aligned} 4d = ((((4n^2+1)u-4n)u+4n+1)u-4)u+4n^2, \end{aligned}$$

(24)

where $n = h_y$. We propose an efficient calculation algorithm for 4d, as shown in Table 6. The total calculation costs of the final exponentiation are summarized in Table 7. Compare with the original GMT672 final exponentiation hard part, our calculation order increased $2s_6$ reduced $5m_6$.

Table 6. Calculation of the raised power of GMT8-542 hard part-4d

Table 7. $\tau _2$ and $\tau _4$ final exponentiation costs.

Table 8. Pairing total costs

6 Implementation Results

To confirm the efficiency of the proposed methods, all the towers shown in Table 3 were implemented for ate pairing cost and speed comparison. The software developed computes bilinear pairings based on the algorithms introduced in Sect. 2.3. In this section, the features of the software libraries used are initially introduced. Furthermore, the pairing implementation results with detailed calculation costs are presented.

6.1 Multi-precision Libraries and Implementation Features

As mentioned above, two libraries (mcl [14] and GMP) are used, which are combined in this work. mcl is a library for pairing-based cryptography, mainly supporting the optimal ate pairing over BN curves and BLS12-381 curves. This library is available on almost all x32 and x64 architecture available platforms. The implementation conducted in this work mainly uses the mpn function group of the GNU multiple precision (GMP) Library called by the C++ language, although some core operations such as multiplication, modulo, addition and bit shift are replaced by mcl functions. The multiplication in $\mathbb {F}_p$ is performed using the Montgomery multiplication techniques.

6.2 Pairing Benchmark Results

Miller’s algorithm and final exponentiation costs are summarized in Table 8. It can be observed that the proposed towers $\tau _2$ and $\tau _4$ exhibit lower costs than $\tau _1$ and $\tau _3$ by applying all the techniques previously described. Specifically, compared with $\tau _1$ and $\tau _2$, they are addition almost 6% more efficient because of the addition cost reduced Karatsuba complex method. Although, $\tau _4$ exhibits an approximate 2% higher costs due to the specially of type-I AOPF but it has lower addition in total. The implementation results are presented in Table 9. The program was compiled using the Clang++12 with the compile option $\texttt {-Ofast -march=native}$. The benchmarks were obtained using an i7-8700 (base clock 3.2 GHz, boost 4.3 GHz) computer.

The proposed pairing computation over the GMT6-672 and GMT8-542 curves is achieved in 0.99 and 1.12 ms, respectively, with Turbo Boost enabled. The construction of tower $\tau _2$ is 5.2% faster than $\tau _1$. Moreover, the construction of tower $\tau _4$ is 2% faster than that of $\tau _3$ due to the addition reduction. It is also observed that $\tau _4$ has this feature which does not require any squaring in $\mathbb {F}_p$, which is an interesting result. A comparison with the GMT paper estimation results is also provided. A comparison between our implementation result and the GMT paper estimation results is provided in Table 9.

Table 9. Implementation results obtained using an i7-8700 CPU (3.2 GHz Turbo Boost off, 4.3 GHz on) computer compared with the GMT paper estimation results

Our implementation results are Benchmarked in the same environment as the GMT paper estimation results. It is observed that the GMT6-672 curve with tower $\tau _2$, our results are achieved faster by approximately 6% than the GMT paper estimation results. For the GMT8-542 curve with tower $\tau _4$, our results are achieved by 0.116 ms slower than the GMT paper estimation results.

7 Conclusion and Future Work

The following results can be concluded:

• 1. After reviewing the GMT6 and GMT8 curve parameters and classes of the existed extension fields, two different types of towers for newly emerged pairing-friendly curves were proposed. Since the GMT6 curve original characteristic is considered sufficiently efficient, a unique and efficient tower construction consisting of nested OEF was proposed. This scheme is suitable to the minimal addition karatsuba complex method. For the GMT8 curve, the existed parameters cannot achieve the best performance. Thus, we reexplored the characteristic and proposed a new set of parameters with only 2 less bits suitable with the type-I AOPF.

• 2. To the best of the authors’ knowledge, complete and efficient software implementations of pairings for the GMT6 and GMT8 curves have not been reported. The cost of the recommended Miller’s algorithm with a twist on the available rational functions of pairings was presented. For the final exponentiation, the polynomials were recalculated, and the costs for both curves were re-evaluated. The implementation results suggested that the GMT6 and GMT8 curves are excellent and efficient candidates for 128-bit security pairing applications.