Keywords

1 Introduction

From the very beginning of the cryptosystems that utilizes elliptic curve pairing; proposed independently by Sakai et al. [18] and Joux [10], has unlocked numerous novel ideas to researchers. Many researchers tried to find out security protocol that exploits pairings to remove the need of certification by a trusted authority. In this consequence, several ingenious pairing based encryption scheme such as ID-based encryption scheme by Boneh and Franklin [5] and group signature authentication by Nakanishi et al. [16] has come into the focus. In such outcome, Ate-based pairings such as Ate [6], Optimal-ate [22], twisted Ate [14], R-ate [13], and \(\chi \)-Ate [17] pairings and their applications in cryptosystems have caught much attention since they have achieved quite efficient pairing calculation. But it has always been a challenge for researchers to make pairing calculation more efficient for being used practically as pairing calculation is regarded as quite time consuming operation.

Bilinear pairing operation consist of two predominant parts, named as Miller’s loop and final exponentiation. Finding pairing friendly curves [8] and construction of efficient extension field arithmetic are the ground work for any pairing operation. Many research has been conducted for finding pairing friendly curves [3, 7] and efficient extension field arithmetic [2]. Some previous work on optimizing the pairing algorithm on pairing friendly curve such Optimal Ate pairing by Matsuda et al. [14] on Barreto-Naehrig (BN) curve [4] is already carried out. The previous work of Mori et al. [15] has showed the pseudo 8-sparse multiplication to efficiently calculate Miller’s algorithm defined over BN curve. Apart from it, Aranha et al. [1] has improved Optimal Ate pairing over KSS curve for 192 bit security level by utilizing the relation \(t(\chi ) - 1 \equiv \chi + 3p(\chi ) \bmod r(\chi )\) where \(t(\chi )\) is the Frobenius trace of KSS curve, \(\chi \) is an integer also known as mother parameter, \(p(\chi )\) is the prime number and \(r(\chi )\) is the order of the curve. This paper has exclusively focused on efficiently calculating the Miller’s loop of Optimal Ate pairing defined over KSS curve [11] for 192-bit security level by applying pseudo 12-sparse multiplication technique along with other optimization approaches. The parameter settings recommended in [1] for 192 bit security on KSS curve is used in the simulation implementation. But in the recent work, Kim et al. [12] has suggested to update the key sizes associated with pairing-based cryptography due to the new development of discrete logarithm problem over finite field. The parameter settings of [1] doesn’t end up at the 192 bit security level according to [12]. However the parameter settings of [1] is primarily adapted in this paper in order to show the resemblance of the proposal with the experimental result.

In general, pairing is a bilinear map from two rational point groups \(\mathbb {G}_{1}\) and \(\mathbb {G}_{2}\) to a multiplicative group \(\mathbb {G}_{3}\) [21]. When KSS pairing-friendly elliptic curve of embedding degree \(k=18\) is chosen for Ate-based pairing, then the bilinear map is denoted by \(\mathbb {G}_{1} \times \mathbb {G}_{2} \rightarrow \mathbb {G}_{3}\), where \(\mathbb {G}_{1} \subset E(\mathbb {F}_p)\), \(\mathbb {G}_{2} \subset E(\mathbb {F}_{p^{18}})\) and \(\mathbb {G}_{3} \subset \mathbb {F}^*_{p^{18}}\) and p denotes the characteristic and E is the curve defined over corresponding extension field \(\mathbb {F}_{p^k}\). Rational point in \(\mathbb {G}_{2} \subset E(\mathbb {F}_{p^{18}})\) has a special vector representation where out of 18 coefficients 3 continuous coefficients are non-zero and the others are zero. By utilizing such representation along with the sextic twisted isomorphic sub-field property of \(\mathbb {F}_{p^{18}}\), this paper has computed the elliptic curve doubling and elliptic curve addition in the Miller’s algorithm as \(\mathbb {F}_{p^3}\) arithmetic without any explicit mapping from \(\mathbb {F}_{p^{18}}\) to \(\mathbb {F}_{p^3}\).

Finally this paper proposes pseudo 12-sparse multiplication in affine coordinates for line evaluation in the Miller’s algorithm by considering the fact that multiplying or dividing the result of Miller’s loop calculation by an arbitrary non-zero element does not change the result as the following final exponentiation cancels the effect of multiplication or division. Following the division by a non-zero element, one of the 7 non-zero coefficients (which is a combination of 1 and 2 \(\mathbb {F}_{p^3}\) coefficients) becomes 1 that yields calculation efficiency. The calculation overhead caused from the division is canceled by isomorphic mapping with a quadratic and cubic residue in . This paper doesn’t end up by giving only the theoretic proposal of improvement of Optimal Ate pairing by pseudo 12-sparse multiplication. In order to evaluate the theoretic proposal, this paper shows some experimental results with recommended parameter settings.

2 Fundamentals

This section briefly reviews the fundamentals of KSS curve [11], towering extension field with irreducible binomials [2], sextic twist, pairings and sparse multiplication [15].

2.1 KSS Curve

Kachisa-Schaefer-Scott (KSS) curve [11] is a non supersingular pairing friendly elliptic curve of embedding degree 18. The equation of KSS curve defined over \(\mathbb {F}_{p^{18}}\) is given as follows:

(1)

together with the following parameter settings,

$$\begin{aligned}&p(\chi )=(\chi ^8\!\!+\!5\chi ^7\!\!+\!7\chi ^6\!\!+\!37\chi ^5\!\!+\!188\chi ^4\!\!+\!259\chi ^3\!\!+\!343\chi ^2\!\!+\!1763\chi \!\!+\!2401)/21,\end{aligned}$$
(2a)
$$\begin{aligned}&r(\chi )=(\chi ^6\!\!+\!37\chi ^3\!\!+\!343)/343,\end{aligned}$$
(2b)
$$\begin{aligned}&t(\chi )\,=(\chi ^4\!\!+\!16\chi \!\!+\!7)/7, \end{aligned}$$
(2c)

where \(b \ne 0\), \(x,y \in \mathbb {F}_{p^{18}}\) and characteristic p (prime number), Frobenius trace t and order r are obtained systematically by using the integer variable \(\chi \), such that \(\chi \equiv 14\) (mod 42).

2.2 Towering Extension Field

In extension field arithmetic, higher level computations can be improved by towering. In towering, higher degree extension field is constructed as a polynomial of lower degree extension fields. Since KSS curve is defined over \(\mathbb {F}_{p^{18}}\), this paper has represented extension field \(\mathbb {F}_{p^{18}}\) as a tower of sub-fields to improve arithmetic operations. In some previous works, such as Bailey et al. [2] explained tower of extension by using irreducible binomials. In what follows, let \((p-1)\) be divisible by 3 and c is a certain quadratic and cubic non residue in . Then for KSS-curve [11], where \(k=18\), \(\mathbb {F}_{p^{18}}\) is constructed as tower field with irreducible binomial as follows:

(3)

Here isomorphic sextic twist of KSS curve defined over \(\mathbb {F}_{p^{18}}\) is available in the base extension field \(\mathbb {F}_{p^3}\).

2.3 Sextic Twist

Let z be a certain quadratic and cubic non residue \(z \in \mathbb {F}_{p^{3}}\). The sextic twisted curve \(E'\) of KSS curve E defined in Eq. (1) and their isomorphic mapping \(\psi _6\) are given as follows:

(4)

where Ker(\(\cdot \)) denotes the kernel of the mapping. Frobenius mapping \(\pi _p\) for rational point is given as

$$\begin{aligned} \pi _p : (x,y) \longmapsto (x^p,y^p). \end{aligned}$$
(5)

The order of the sextic twisted isomorphic curve \(\#E'(\mathbb {F}_{p^3})\) is also divisible by the order of KSS curve E defined over denoted as r. Extension field arithmetic by utilizing the sextic twisted sub-field curve \(E'(\mathbb {F}_{p^{3}})\) based on the isomorphic twist can improve pairing calculation. In this paper, \(E'(\mathbb {F}_{p^{3}})[r]\) shown in Eq. (4) is denoted as \(\mathbb {G}_2'\).

Isomorphic mapping between E( ) and Let us consider is isomorphic to and \(\hat{z}\) as a quadratic and cubic residue in . Mapping between and is given as follows:

(6)

2.4 Pairings

As described earlier bilinear pairing requires two rational point groups to be mapped to a multiplicative group. In what follows, Optimal Ate pairing over KSS curve of embedding degree \(k = 18\) is described as follows.

Optimal Ate Pairing. Let us consider the following two additive groups as \(\mathbb {G}_{1}\) and \(\mathbb {G}_{2}\) and multiplicative group as \(\mathbb {G}_{3}\). The Ate pairing \(\alpha \) is defined as follows:

(7)

where \(\mathbb {G}_{1} \subset E(\mathbb {F}_p)\) and \(\mathbb {G}_{2} \subset E(\mathbb {F}_{p^{18}})\) in the case of KSS curve.

Let \(P \in \mathbb {G}_{1}\) and \(Q\in \mathbb {G}_{2}\), Ate pairing \(\alpha (Q,P)\) is given as follows.

$$\begin{aligned} \alpha (Q,P)=f_{t-1,Q}(P)^{\frac{p^k-1}{r}}, \end{aligned}$$
(8)

where \(f_{t-1,Q}(P)\) symbolize the output of Miller’s algorithm. The bilinearity of Ate pairing is satisfied after calculating the final exponentiation. It is noted that improvement of final exponentiation is not the focus of this paper. Several works [19, 20] have been already done for efficient final exponentiation.

The previous work of Aranha et al. [1] has mentioned about the relation \(t(\chi ) - 1 \equiv \chi + 3p(\chi ) \bmod r(\chi )\) for Optimal Ate pairing. Exploiting the relation, Optimal Ate pairing on the KSS curve is defined by the following representation.

$$\begin{aligned} (Q,P)=(f_{\chi ,Q}\cdot f_{3,Q}^p\cdot l_{[\chi ]Q,[3p]Q})^{\frac{p^{18}-1}{r}}, \end{aligned}$$
(9)

where \(\chi \) is the mother parameter. The calculation procedure of Optimal Ate pairing is shown in Algorithm 1. In what follows, the calculation steps from 1 to 5 shown in Algorithm 1 is identified as Miller’s loop. Steps 3 and 5 are line evaluation along with elliptic curve doubling and addition. These two steps are key steps to accelerate the loop calculation. As an acceleration technique pseudo 12-sparse multiplication is proposed in this paper.

2.5 Sparse Multiplication

In the previous work, Mori et al. [15] has substantiated the pseudo 8-sparse multiplication for BN curve. Adapting affine coordinates for representing rational points, we can apply Mori’s work in the case of KSS curve. The doubling phase and addition phase in Miller’s loop can be carried out efficiently by the following calculations. Let \(P=(x_P,y_P)\), \(T=(x,y)\) and \(Q=(x_2,y_2)\in E'(\mathbb {F}_{p^{3}})\) be given in affine coordinates, and let \(T+Q=(x_3,y_3)\) be the sum of T and Q.

Step 3: Elliptic curve doubling phase ( \(\varvec{T = Q}\) )

(10)

where \(\overline{x}_P=-x_P\) will be pre-computed. Here \(l_{T,T}(P)\) denotes the tangent line at the point T.

Step 5: Elliptic curve addition phase ( \(\varvec{T\ne Q}\) )

(11)

where \(\overline{x}_P=-x_P\) will be pre-computed. Here \(l_{T,Q}(P)\) denotes the tangent line between the point T and Q.

Analyzing Eqs. (10) and (11), we get that E and \(Cx_P\) are calculated in \(\mathbb {F}_{p^3}\). After that, the basis element 1, v and \(\theta \) identifies the position of \(y_P\), E and \(Cx_P\) in \(\mathbb {F}_{p^{18}}\) vector representation. Therefore vector representation of \(l_{\psi _6(T),\psi _6(T)}(P)\in \mathbb {F}_{p^{18}}\) consists of 18 coefficients. Among them at least 11 coefficients are equal to zero. In the other words, only 7 coefficients , \(Cx_P\in \mathbb {F}_{p^{3}}\) and \(E\in \mathbb {F}_{p^{3}}\) are perhaps to be non-zero. \(l_{\psi _6(T),\psi _6(Q)}(P)\in \mathbb {F}_{p^{18}}\) also has the same vector structure. Thus, the calculation of multiplying \(l_{\psi _6(T),\psi _6(T)}(P)\in \mathbb {F}_{p^{18}}\) or \(l_{\psi _6(T),\psi _6(Q)}(P)\in \mathbb {F}_{p^{18}}\) is called sparse multiplication. In the above mentioned instance especially called 11-sparse multiplication. This sparse multiplication accelerates Miller’s loop calculation as shown in Algorithm 1. This paper comes up with pseudo 12-sparse multiplication.

figure a

3 Improved Optimal Ate Pairing for KSS Curve

In this section we describe the main proposal. Before going to the details, at first we give an overview of the improvement procedure of Optimal Ate pairing in KSS curve. The following two ideas are proposed in order to efficiently apply 12-sparse multiplication on Optimal Ate pairing on KSS curve.

  1. 1.

    In Eqs. (10) and (11) among the 7 non-zero coefficients, one of the non-zero coefficients is . And \(y_P\) remains uniform through Miller’s loop calculation. Thereby dividing both sides of those Eqs. (10) and (11) by \(y_P\), the coefficient becomes 1 which results in a more efficient sparse multiplication by \(l_{\psi _6(T),\psi _6(T)}(P)\) or \(l_{\psi _6(T),\psi _6(Q)}(P)\). This paper calls it pseudo 12-sparse multiplication.

  2. 2.

    Division by \(y_P\) in Eqs. (10) and (11) causes a calculation overhead for the other non-zero coefficients in the Miller’s loop. To cancel this additional cost in Miller’s loop, the map introduced in Eq. (6) is applied.

It is to be noted that this paper doesn’t focus on making final exponentiation efficient in Miller’s algorithm since many efficient algorithms are available. From Eqs. (10) and (11) the above mentioned ideas are introduced in details.

3.1 Pseudo 12-Sparse Multiplication

As said before \(y_P\) shown in Eq. (10) is a non-zero elements in . Thereby, dividing both sides of Eq. (10) by \(y_P\) we obtain as follows:

$$\begin{aligned} y_P^{-1}l_{T,T}(P)=1+Ey_P^{-1}v-C(x_Py_P^{-1})\theta . \end{aligned}$$
(12)

Replacing \(l_{T,T}(P)\) by the above \(y_P^{-1}l_{T,T}(P)\), the calculation result of the pairing does not change, since \(final\;exponentiation\) cancels . One of the non-zero coefficients becomes 1 after the division by \(y_P\), which results in more efficient vector multiplications in Miller’s loop. This paper calls it \(pseudo\;12-sparse\;multiplication\). Algorithm 2 introduces the detailed calculation procedure of pseudo 12-sparse multiplication.

figure b

3.2 Line Calculation in Miller’s Loop

The comparison of Eqs. (10) and (12) shows that the calculation cost of Eq. (12) is little bit higher than Eq. (10) for \(Ey_P^{-1}\). The cancellation process of \(x_Py_P^{-1}\) terms by utilizing isomorphic mapping is introduced next. The \(x_Py_P^{-1}\) and \(y_P^{-1}\) terms are pre-computed to reduce execution time complexity. The map introduced in Eq. (6) can find a certain isomorphic rational point such that

$$\begin{aligned} x_{\hat{P}}y_{\hat{P}}^{-1}=1. \end{aligned}$$
(13)

Here the twist parameter z of Eq. (4) is considered to be \(\hat{z}=(x_Py_P^{-1})^6\) of Eq. (6), where \(\hat{z}\) is a quadratic and cubic residue in and \(\hat{E}\) denotes the KSS curve defined by Eq. (6). From the isomorphic mapping Eq. (4), such z is obtained by solving the following equation considering the input \(P(x_P,y_P)\).

$$\begin{aligned} z^{1/3}x_P=z^{1/2}y_P, \end{aligned}$$
(14)

Afterwards the is given as

$$\begin{aligned} \hat{P}(x_{\hat{P}},y_{\hat{P}})=(x_P^3y_P^{-2},x_P^3y_P^{-2}). \end{aligned}$$
(15)

As the x and y coordinates of \(\hat{P}\) are the same, \(x_{\hat{P}}y_{\hat{P}}^{-1}=1\). Therefore, corresponding to the map introduced in Eq. (6), first mapping not only P to \(\hat{P}\) shown above but also Q to \(\hat{Q}\) shown below.

$$\begin{aligned} \hat{Q}(x_{\hat{Q}},y_{\hat{Q}})=(x_P^2y_P^{-2}x_Q,x_P^3y_P^{-3}y_Q). \end{aligned}$$
(16)

When we define a new variable \(L=(x_P^{-3}y_P^2)=y_{\hat{P}}^{-1}\), the line evaluations, Eqs. (10) and (11) become the following calculations. In what follows, let , \(T=(x,y)\) and \(Q=(x_2,y_2)\in E'(\mathbb {F}_{p^{3}})\) be given in affine coordinates and let \(T+Q=(x_3,y_3)\) be the sum of T and Q.

Step 3: Doubling phase ( \(\varvec{T=Q}\) )

(17)

where \(L=y_{\hat{P}}^{-1}\) will be pre-computed.

Step 5: Addition phase ( \(\varvec{T\ne Q}\) )

(18)

where \(L=y_{\hat{P}}^{-1}\) will be pre-computed.

As we compare the above equation with to Eqs. (10) and (11), the third term of the right-hand side becomes simple since \(x_{\hat{P}}y_{\hat{P}}^{-1}=1\).

In the above procedure, calculating \(\hat{P}\), \(\hat{Q}\) and L by utilizing \(x_P^{-1}\) and \(y_P^{-1}\) will create some computational overhead. In spite of that, calculation becomes efficient as it is performed in isomorphic group together with pseudo 12-sparse multiplication in the Miller’s loop. Improvement of Miller’s loop calculation is presented by experimental results in the next section.

4 Cost Evaluation and Experimental Result

This section shows some experimental results with evaluating the calculation costs in order to the signify efficiency of the proposal. It is to be noted here that in the following discussions “Previous method” means Optimal Ate pairing with no use the sparse multiplication, “11-sparse multiplication” means Optimal Ate pairing with 11-sparse multiplication and “Proposed method” means Optimal Ate pairing with Pseudo 12-sparse multiplication.

4.1 Parameter Settings and Computational Environment

In the experimental simulation, this paper has considered the 192 bit security level for KSS curve. Table 1 shows the parameters settings suggested in [1] for 192 bit security over KSS curve. However this parameter settings does not necessarily comply with the recent suggestion of key size by Kim et al. [12] for 192 bit security level. The sole purpose to use this parameter settings in this paper is to compare the literature with the experimental result.

Table 1. Parameters
Full size table

To evaluate the operational cost and to compare the execution time of the proposal based on the recommended parameter settings, the following computational environment is considered. Table 2 shows the computational environment.

Table 2. Computing environment
Full size table

4.2 Cost Evaluation

Let us consider m, s, a and i to denote the times of multiplication, squaring, addition and inversion . Similarly, \(\tilde{m},\tilde{s},\tilde{a}\) and \(\tilde{i}\) denote the number of multiplication, squaring, addition and inversion \(\in \mathbb {F}_{p^{3}}\) and \(\hat{m},\hat{s},\hat{a}\) and \(\hat{i}\) to denote the count of multiplication, squaring, addition and inversion \(\in \mathbb {F}_{p^{18}}\) respectively. Tables 3 and 4 show the calculation costs with respect to operation count.

Table 3. Operation count of line evaluation
Full size table
Table 4. Operation count of multiplication
Full size table

By analyzing the Table 4 we can find that 11-sparse multiplication requires 18 more multiplication in than pseudo 12-sparse multiplication.

4.3 Experimental Result

Table 5 shows the calculation times of Optimal Ate pairing respectively. In this execution time count, the time required for final exponentiation is excluded. The results (time count) are the averages of 10000 iterations on PC respectively. According to the experimental results, pseudo 12-sparse contributes to a few percent acceleration of 11-sparse.

Table 5. Calculation time of Optimal Ate pairing at the 192-bit security level
Full size table

5 Conclusion and Future Works

This paper has proposed pseudo 12-sparse multiplication for accelerating Optimal Ate pairing on KSS curve. According to the calculation costs and experimental results shown in this paper, the proposed method can calculate Optimal Ate pairing more efficiently. As a future work we would like to evaluate the efficiency in practical case by implementing it in some pairing based protocols.