Efficient Scalar Multiplication for Ate Based Pairing over KSS Curve of Embedding Degree 18

Abstract

Efficiency of the next generation pairing based security protocols rely not only on the faster pairing calculation but also on efficient scalar multiplication on higher degree rational points. In this paper we proposed a scalar multiplication technique in the context of Ate based pairing with Kachisa-Schaefer-Scott (KSS) pairing friendly curves with embedding degree $k = 18$ at the 192-bit security level. From the systematically obtained characteristics p, order r and Frobenious trace t of KSS curve, which is given by certain integer z also known as mother parameter, we exploit the relation $\#E({\mathbb {F}}_{p}) = p+1-t$ mod r by applying Frobenius mapping with rational point to enhance the scalar multiplication. In addition we proposed z-adic representation of scalar s. In combination of Frobenious mapping with multi-scalar multiplication technique we efficiently calculate scalar multiplication by s. Our proposed method can achieve 3 times or more than 3 times faster scalar multiplication compared to binary scalar multiplication, sliding-window and non-adjacent form method.

1 Introduction

The intractability of Elliptic Curve Discrete Logarithm Problem (ECDLP) spurs on many innovative pairing based cryptographic protocols. Pairing based cryptography is considered to be the basis of next generation security. Recently a number of unique and innovative pairing based cryptographic applications such as identity based encryption scheme [17], broadcast encryption [8] and group signature authentication [7] surge the popularity of pairing based cryptography. In such consequence Ate-based pairings such as Ate [9] and Optimal-ate [20], twisted Ate [13] and $\chi$-Ate [15] pairings has gained much attention. To make such cryptographic applications practical, these pairings need to be computed efficiently and fast. This paper focuses on such Ate-based pairings.

Pairing is a bilinear map from two rational point ${\mathbb {G}}_{1}$ and ${\mathbb {G}}_{2}$ to a multiplicative group ${\mathbb {G}}_{3}$ [19] typically denoted by ${\mathbb {G}}_{1} \times {\mathbb {G}}_{2} \rightarrow {\mathbb {G}}_{3}$. In the case of Ate-based pairing, ${\mathbb {G}}_{1}$, ${\mathbb {G}}_{2}$ and ${\mathbb {G}}_{3}$ are defined as follows:

$$\begin{aligned} {\mathbb {G}}_{1}= & {} E({\mathbb {F}}_{p^{k}}) [r] \cap \text {Ker}(\pi _p - [1]), \\ {\mathbb {G}}_{2}= & {} E({\mathbb {F}}_{p^{k}}) [r] \cap \text {Ker}(\pi _p - [p]), \\ {\mathbb {G}}_{3}= & {} {{\mathbb {F}}^{*}}_{\!\!\!p^{k}}/({{\mathbb {F}}^{*}}_{\!\!\!p^{k}})^r, \end{aligned}$$

$$\begin{aligned} \alpha : {\mathbb {G}}_{1} \times {\mathbb {G}}_{2} \rightarrow {\mathbb {G}}_{3}, \end{aligned}$$

where $\alpha$ denotes Ate pairing. In general, pairings are only found in certain extension field $\mathbb {F}_{p^k}$, where p is the prime number, also know as characteristics and the minimum extension degree k is called embedding degree. The rational points $E(\mathbb {F}_{p^k})$ are defined over a certain pairing friendly curve of embedded extension field of degree k. Security level of pairing based cryptography depends on the sizes of both r and $p^k$, where r generally denotes the largest prime number that divides the order $\#E(\mathbb {F}_{p})$. The next generation security of pairing-based cryptography needs $\log _2 r \approx 256$ bits and $\log _2 p^k \approx 3000$ to 5000 bits. Therefore taking care of $\rho = (\log _2 p)/(\log _2 r)$, k needs to be 12 to 20. This paper has considered Kachisa-Schaefer-Scott (KSS) [12] pairing friendly curves of embedding degree $k=18$ described in [10]. Pairing on KSS curve is considered to be the basis of next generation security as it conforms 192-bit security level. Making the pairing practical over KSS curve depends on several factors such as efficient pairing algorithm, efficient extension field arithmetic and efficiently performing scalar multiplication. Many researches have conducted on efficient pairing algorithms [4] and curves [5] along with extension field arithmetic [2]. This paper focuses on efficiently performing scalar multiplication in ${\mathbb {G}}_{2}$ by scalar s, since scalar multiplication is required repeatedly in cryptographic calculation. Scalar multiplication is also considered to be the one of the most time consuming operation in cryptographic scene. Moreover in asymmetric pairing such as Ate-based pairing, scalar multiplication in ${\mathbb {G}}_{2}$ is important as no mapping function is explicitly given between ${\mathbb {G}}_{1}$ to ${\mathbb {G}}_{2}$. By the way, as shown in the definition, ${\mathbb {G}}_{1}$ is a set of rational points defined over prime field and there are many researches for efficient scalar multiplication in ${\mathbb {G}}_{1}$.

Scalar multiplication by s means $(s-1)$ times elliptic additions of a given rational point on the elliptic curve. This elliptic addition is not as simple as addition of extension field, but it requires 3 multiplications plus an inversion of the extension field. General approaches to accelerate scalar multiplication are log-step algorithm such as binary and non-adjacent form (NAF) methods, but more efficient approach is to use Frobenius mapping in the case of ${\mathbb {G}}_{2}$ that is defined over ${\mathbb {F}}_{p^{k}}$. Frobenious map $\pi : (x,y) \mapsto (x^p,y^p)$ is the p-th power of the rational point (x, y) defined over $\mathbb {F}_{p^k}$. In this paper we also exploited the Frobenious trace t, $t = p+1- \#E(\mathbb {F}_{p})$ defined over KSS curve. In the previous work on optimal-ate pairing, Aranha et al. [1] derived an important relation: $z \equiv -3p + p^4 \bmod {r}$, where z is the mother parameter of KSS curve and z is about six times smaller than the size of order r. We have utilized this relation to construct z-adic representation of scalar s which is introduced in Sect. 3. In addition with Frobenius mapping and z-adic representation of s, we applied the multi-scalar multiplication technique to compute elliptic curve addition in parallel in the proposed scalar multiplication. We have compared our proposed method with three other well studied methods named binary method, sliding-window method and non-adjacent form method. The comparison shows that our proposed method is at least 3 times or more than 3 times faster than above mentioned methods in execution time. The comparison also reveals that the proposed method requires more than 5 times less elliptic curve doubling than any of the compared methods.

As shown in the previous work of scalar multiplication on sextic twisted BN curve by Nogami et al. [16], we can consider sub-field sextic twisted curve in the case of KSS curve of embedding degree 18. Let us denote the sub-field sextic twisted curve by $E'$. It will include sextic twisted isomorphic rational point group denoted as ${\mathbb {G}}_{2}'$. In KSS curve, ${\mathbb {G}}_{2}$ is defined over $\mathbb {F}_{p^{18}}$ whereas its sub-field isomorphic group ${\mathbb {G}}_{2}'$ is defined over $\mathbb {F}_{p^3}$. Important feature of this sextic twisted isomorphic group is, all the scalar multiplication in ${\mathbb {G}}_{2}$ is mapped with ${\mathbb {G}}_{2}'$ and it can be efficiently carried out by applying skew Frobenious map. Then, the resulted points can be re-mapped to ${\mathbb {G}}_{2}$ in $\mathbb {F}_{p^{18}}$. This above mentioned skew Frobenious mapping in sextic twisted isomorphic group will calculate more faster scalar multiplication. However, the main focus of this paper is presenting the process of splitting the scalar into z-adic representation and applying Frobenius map in combination with multi-scalar multiplication technique.

2 Preliminaries

In this section we will go through the fundamental background of elliptic curves and its operations. We will briefly review elliptic curve scalar multiplication. After that pairing friendly curve of embedding degree $k=18$, i.e., KSS curve and its properties will be introduced briefly.

2.1 Elliptic Curve [21]

Let ${\mathbb {F}}_{p}$ be a prime field. Elliptic curve over ${\mathbb {F}}_{p}$ is defined as,

$$\begin{aligned} E/{\mathbb {F}}_{p}: y^2=x^3+ax+b, \end{aligned}$$

(1)

where $4a^3+27b^2 \ne 0$ and $a,b \in {\mathbb {F}}_{p}$. Points satisfying Eq. (1) are known as rational points on the curve.

Point Addition. Let $E({\mathbb {F}}_{p})$ be the set of all rational points on the curve defined over ${\mathbb {F}}_{p}$ and it includes the point at infinity denoted by $\mathcal {O}$. The order of $E(\mathbb {F}_{p})$ is denoted by $\#E(\mathbb {F}_{p})$ where $E(\mathbb {F}_{p})$ forms an additive group for the elliptic addition. Let us consider two rational points $L = (x_l, y_l)$, $M = (x_m, y_m)$, and their addition $N = L + M$, where $\textit{N} = (x_n, y_n)$ and $L, M, N\in E({\mathbb {F}}_{p})$. Then, the x and y coordinates of N is calculated as follows:

$$\begin{aligned} (x_n ,y_n)= & {} ((\lambda ^2-x_l-x_m ), (x_l-x_n)\lambda - y_l), \end{aligned}$$

(2a)

where $\lambda$ is given as follows:

$$\begin{aligned} \textstyle \lambda = {\left\{ \begin{array}{ll} \textstyle (y_m - y_l)(x_m -x_l)^{-1} \quad \text{( }L \ne M \text{ and } x_m \ne x_l\text{) },\\ \\ \textstyle (3x_l^2+a)(2y_l)^{-1} \quad \text{( }N = M \text{ and } y_l\ne 0\text{) }\,, \end{array}\right. } \end{aligned}$$

(2b)

$\lambda$ is the tangent at the point on the curve and $\mathcal O$ it the additive unity in $E({\mathbb {F}}_{p})$. When $L \ne M$ then $L+M$ is called elliptic curve addition (ECA). If $L=M$ then $L+M=2L$, which is known as elliptic curve doubling (ECD).

Scalar Multiplication. Let s is a scalar where $0 \le s < r$, where r is the order of the target rational point group. Scalar multiplication of rational points M, denoted as [s]M can be done by $(s-1)$-times additions of M as,

$$\begin{aligned}{}[s]M = \underbrace{M+M+ \cdots +M}_{s-1 \quad \text{ times } \text{ additions }}. \end{aligned}$$

(3)

If $s = r$, where r is the order of the curve then $[r]M = \mathcal {O}$. When $[s]M = N$, if s is unknown, then the solving s from M and N is known as elliptic curve discrete logarithm problem (ECDLP). The security of elliptic curve cryptography lies on the difficulty of solving ECDLP.

2.2 KSS Curve

KSS curve is a non super-singular pairing friendly elliptic curve of embedding degree 18 [12]. The equation of KSS curve defined over $\mathbb {F}_{p^{18}}$ is given by

$$\begin{aligned} E:Y^2=X^3+b, \quad {(b \in {\mathbb {F}}_{p})}, \end{aligned}$$

(4)

where $b \ne 0$ and $X,Y \in \mathbb {F}_{p^{18}}$. Its characteristic p, Frobenius trace t and order r are given systematically by using an integer variable z as follows:

$$\begin{aligned} p(z)= & {} (z^8 +5z^7 +7z^6 +37z^5 +188z^4 +259z^3 +343z^2 \nonumber \\&+1763z+2401)/21,\end{aligned}$$

(5a)

$$\begin{aligned} r(z)= & {} (z^6 + 37z^3 + 343)/343, \end{aligned}$$

(5b)

$$\begin{aligned} t(z)= & {} (z^4 + 16z + 7)/7, \end{aligned}$$

(5c)

where z is such that $z \equiv 14$ (mod 42) and the co-factor is $\rho = (\log _2 p/\log _2 r)$ is about 4/3. The order of rational points $\#E(\mathbb {F}_{p^{18}})$ on KSS curve can be obtained by the following relation.

$$\begin{aligned} \#E(\mathbb {F}_{p^{18}}) = p^{18}+1-t_{18}, \end{aligned}$$

(6)

where $t_{18} = \alpha ^{18}+\beta ^{18}$ and $\alpha$, $\beta$ are complex numbers such that $\alpha +\beta = t$ and $\alpha \beta =p$. Since Aranha et al. [1] and Scott et al. [18] has proposed the size of the characteristics p to be 508 to 511-bit with order r of 384-bit for 192-bit security level, therefore this paper considered $p=511$-bit.

Frobenius Mapping of Rational Point in ${\varvec{E}}(\mathbb {F}_{p^{18}})$ . Let (x, y) be the rational point in $E(\mathbb {F}_{p^{18}})$. Frobenious map $\pi _p : (x,y) \mapsto (x^p,y^p)$ is the p-th power of the rational point defined over $\mathbb {F}_{p^{18}}$. Some previous work [11] has been done on constructing Frobenius mapping and utilizing it to calculate scalar multiplication. Nogami et al. [16] showed efficient scalar multiplication in the context of Ate-based pairing in BN curve of embedding degree $k=12$. This paper has exploited Frobenius mapping for efficient scalar multiplication for the case of KSS curve.

2.3 $\mathbb {F}_{p^{18}}$ Extension Field Arithmetic

In context of pairing, it is required to perform arithmetic in higher extension fields, such as $\mathbb {F}_{p^k}$ for moderate value of k [19]. Therefore it is important to construct the field as a tower of extension fields [6] to perform arithmetic operation efficiently. Higher level computations can be calculated as a function of lower level computations. Because of that an efficient implementation of lower level arithmetic results in the good performance of arithmetic in higher degree fields.

In this paper extension field $\mathbb {F}_{p^{18}}$ is represented as a tower of sub field to improve arithmetic operations. In some previous works, such as Bailey et al. [3] explained tower of extension by using irreducible binomials. In what follows, let $(p-1)$ is divisible by 3 and $\theta$ is a quadratic and cubic non residue in ${\mathbb {F}}_{p}$. Then for case of KSS-curve [12], where $k=18$, $\mathbb {F}_{p^{18}}$ is constructed as tower field with irreducible binomial as follows:

$$\begin{aligned} {\left\{ \begin{array}{ll} {\mathbb {F}}_{p^{3}} = {\mathbb {F}}_{p^{}}[i]/(i^3-\theta ), \text {where}\ \theta = 2~\text {is the best choice,} \\ {\mathbb {F}}_{p^{6}} = {\mathbb {F}}_{p^{3}}[v]/(v^2-i), \\ {\mathbb {F}}_{p^{18}} = {\mathbb {F}}_{p^{6}}[w]/(w^3-v). \\ \end{array}\right. } \end{aligned}$$

According to previous work such as Aranha et al. [1], the base extension field is $\mathbb {F}_{p^3}$ for the sextic twist of KSS curve.

3 Efficient Scalar Multiplication

In this section we will introduce our proposal for efficient scalar multiplication in ${\mathbb {G}}_{2}$ rational point for Ate-based pairing on KSS curve. Before going to detailed procedure, an overview about how the proposed method will calculate scalar multiplication efficiently of ${\mathbb {G}}_{2}$ rational point is given.

Overview. At first ${\mathbb {G}}_{1}$, ${\mathbb {G}}_{2}$ and ${\mathbb {G}}_{3}$ groups will be defined. Then a rational point $Q \in {\mathbb {G}}_{2}$ will be considered. In context of KSS curve, properties of Q will be obtained to define the Eq. (9) relation. Next, a scalar s will be considered for scalar multiplication of [s]Q. After that, as Fig. 1, $(t-1)$-adic representation of s will be considered, where s will be divided into two smaller parts $S_H$, $S_L$. The lower bits of s, represented as $S_L$, will be nearly equal to the size of $(t-1)$ while the higher order bits $S_H$ will be the half of the size of $(t-1)$. Next, z-adic representation of $S_H$ and $S_L$ will be considered. Figure 2, shows the z-adic representation from where we find that scalar s is divided into 6 coefficients of z, where the size of z is about 1/4 of that of $(t-1)$ as Eq. (5c). Next we will pre-compute the Frobenius maps of some rational points defined by detailed procedure. As shown in Eq. (12), considering 3 pairs from the coefficients we will apply the mult-scalar multiplication in addition with Frobenious mapping, as shown in Fig. 3 to calculate scalar multiplication efficiently. Later part of this section will provide the detailed procedure of the proposal.

Figure 1 shows $(t-1)$-adic representation of scalar s.

Fig. 1.

$(t-1)$ -adic representation of scalar s.

Figure 2 shows the final z-adic representation of scalar s.

Fig. 2.

z-adic and $(t-1)$-adic representation of scalar s.

Figure 3 shows, an example of multi-scalar multiplication process, implemented in the experiment.

Fig. 3.

Multi-scalar multiplication of s with Frobenius mapping.

${\mathbb {G}}_{1}$, ${\mathbb {G}}_{2}$ and ${\mathbb {G}}_{3}$ groups. In the context of pairing-based cryptography, especially on KSS curve, three groups ${\mathbb {G}}_{1}, {\mathbb {G}}_{2}$, and $\mathbb {G}_3$ are considered. From [14], we define ${\mathbb {G}}_{1}$, ${\mathbb {G}}_{2}$ and ${\mathbb {G}}_{3}$ as follows:

$$\begin{aligned} {\mathbb {G}}_{1}= & {} E({\mathbb {F}}_{p^{k}}) [r] \cap \text {Ker}(\pi _p - [1]), \\ {\mathbb {G}}_{2}= & {} E({\mathbb {F}}_{p^{k}}) [r] \cap \text {Ker}(\pi _p - [p]), \\ {\mathbb {G}}_{3}= & {} {{\mathbb {F}}^{*}}_{\!\!\!p^{k}}/({{\mathbb {F}}^{*}}_{\!\!\!p^{k}})^r, \end{aligned}$$

$$\begin{aligned} \alpha : {\mathbb {G}}_{1} \times {\mathbb {G}}_{2} \rightarrow {\mathbb {G}}_{3}, \end{aligned}$$

(7)

where $\alpha$ denotes Ate pairing. In the case of KSS curve, ${\mathbb {G}}_{1}, {\mathbb {G}}_{2}$ are rational point groups and $\mathbb {G}_3$ is the multiplicative group in $\mathbb {F}_{p^{18}}$. They have the same order r.

Let us consider a rational point $Q\in {\mathbb {G}}_{2} \subset E({\mathbb {F}}_{p^{18}})$. In the case of KSS curve, it is known that Q satisfies the following relations,

$$\begin{aligned} \big [p+1-t\big ]Q= & {} \mathcal O, \nonumber \\ \big [t-1\big ]Q= & {} \big [p\big ]Q. \end{aligned}$$

(8)

$$\begin{aligned}{}[\pi _p -p]Q= & {} \mathcal O, \nonumber \\ \pi _p(Q)= & {} [p]Q. \end{aligned}$$

(9)

Thus, these relations can accelerate a scalar multiplication in ${\mathbb {G}}_{2}$. Substituting [p]Q in Eq. (8) we find $[t-1]Q = \pi _p(Q)$.

z -adic representation of scalar s. From the previous work on optimal-ate pairing, Aranha et al. [1] derived the following relation from parameters Eq. (5a), (5b) and (5c) of KSS curve.

$$\begin{aligned} z+3p-p^4 \equiv 0 \bmod {r}. \end{aligned}$$

(10)

Here z is the mother parameter of KSS curve and z is about six times smaller than the size of order r.

Let us consider scalar multiplication [s]Q, where $0 \le s < r$. From Eq. (5b) we know r is the order of KSS curve where $[r]Q=\mathcal O$. Here, the bit size of s is nearly equal to r. In KSS curve t is 4 / 6 times of r. Therefore, let us first consider $(t-1)$-adic representation of s as follows:

$$\begin{aligned} s = S_H(t-1)+S_L, \end{aligned}$$

(11)

where s will be separated into two coefficients $S_H$ and $S_L$. Size of $S_L$ will be nearly equal to the size of $(t-1)$ and $S_H$ will be about half of $(t-1)$. Now we consider z-adic representation of $S_H$ and $S_L$ as follows:

$$\begin{aligned} S_H= & {} s_5+ s_4, \\ S_L= & {} s_3 z^3+s_2 z^2+s_1 z+s_0. \end{aligned}$$

Finally s can be represented as 6 coefficients as follows:

$$\begin{aligned} s= & {} \sum _{i=0}^{3} s_iz^i + (s_4+s_5z)(t-1),\nonumber \\ s= & {} (s_0+s_1z) + (s_2 +s_3z)z^2 +(s_4+s_5z)(t-1). \end{aligned}$$

(12)

Reducing the Number of ECA and ECD for Calculating $[{\varvec{s}}]{\varvec{Q}}$ . Let us consider a scalar multiplication of $Q \in {\mathbb {G}}_{2}$ in Eq. (12) as follows:

$$\begin{aligned}{}[s]Q = (s_0+s_1z)Q + (s_2 +s_3z)z^2Q +(s_4+s_5z)(t-1)Q. \end{aligned}$$

(13)

Let us denote $z^2Q$, $(t-1)Q$ of Eq. (13) as $Q_1$ and $Q_2$ respectively. From Eqs. (9) and (10) we can derive the $Q_1$ as follows:

$$\begin{aligned} Q_1= & {} z^2 Q, \nonumber \\= & {} (9p^2-6p^5+p^8)Q,\nonumber \\= & {} 9\pi ^2(Q)-6\pi ^5(Q)+\pi ^8(Q). \end{aligned}$$

(14)

Using the properties of cyclotomic polynomial Eq. (14) is simplified as,

$$\begin{aligned} Q_1= & {} 8\pi ^2(Q)-5\pi ^5(Q), \nonumber \\= & {} \pi ^2(8Q)-\pi ^5(5Q). \end{aligned}$$

(15)

And from the Eqs. (8) and (9), $Q_2$ is derived as,

$$\begin{aligned} Q_2 = \pi (Q). \end{aligned}$$

(16)

Substituting Eqs. (15) and (16) in Eq. (13), the following relation is obtained.

$$\begin{aligned} s[Q] = (s_0+s_1z)Q + (s_2 +s_3z)Q_1 +(s_4+s_5z)Q_2. \end{aligned}$$

(17)

Using $z \equiv -3p + p^4$ (mod r) from Eq. (10), z(Q) can be pre-computed as follows:

$$\begin{aligned} z(Q) = \pi (-3Q) +\pi ^4(Q). \end{aligned}$$

(18)

Table 1 shows all the pre-computed values of rational points for the proposed method. In this paper pre-computed rational points are denoted such as $<Q+Q_2>$. Finally applying the multi-scalar multiplication technique in Eq. (17) we can efficiently calculate the scalar multiplication. Figure 3 shows an example of this multiplication. Suppose in an arbitrary index, from left to right, bit pattern of $s_1$, $s_3$, $s_5$ is 101 and at the same index $s_0$, $s_2$, $s_4$ is 111. Therefore we apply the pre-computed points $< z(Q)+z(Q_2)>$ and $<Q+Q_1+Q_2>$ as ECA in parallel. Then we perform ECD and move to the right next bit index to repeat the process until maximum length z-adic coefficient becomes zero.

Table 1. Pre-computed values of rational point for efficient scalar multiplication

As shown in Fig. 3, during scalar multiplication in parallel, we are considering Eq. (12) like 3 pair of coefficients of z-adic representation. If we consider 6-coefficients for parallelization, we will need to calculate $2^6 \times 2$ pre-computed points. The chance of appearing each pre-computed point in parallel calculation will be only once which will make the pre-calculated points redundant.

4 Experimental Result Evaluation

In order to demonstrate the efficiency of the proposal, this section shows some experimental result with the calculation cost. In the experiment we have compared the proposed method with three well studied method of scalar multiplication named binary method, sliding-window method and non-adjacent form (NAF) method.

In the experiment the following parameters are considered for the KSS curve $y^2 = x^3 + 11$.

$$\begin{aligned} z= & {} 65 \text{-bit }, \\ p= & {} 511 \text{-bit }, \\ r= & {} 378 \text{-bit },\\ t= & {} 255 \text{-bit }. \end{aligned}$$

The mother parameter z is also selected accordingly to find out ${\mathbb {G}}_{2}$ rational point Q.

500 scalar numbers of size (about 377-bit) less than order r is generated randomly in the experiment. Then average number of ECA and ECD for the proposed method and the three other methods is calculated for a scalar multiplication. 13 pre-computed ECA is taken into account while the average is calculated for the proposed method. In case of sliding-window method window size 4-bit is considered. Therefore 14 pre-computed ECA is required. In addition, average execution time of the proposed method and the three other methods is also compared.

Table 2 shows the environment, used to experiment and evaluate the proposed method.

Table 2. Computational environment

Table 3. Comparative result of average number of ECA and ECD and execution time in [ms] for scalar multiplication

Analyzing Table 3 we can find that our proposed method requires more than 5 times less ECD than binary method, sliding-window method and NAF method. The number of ECA is also reduced in the proposed method by about 30% than binary method.

In this experiment, execution time may seems slower than other efficient algorithm such as Montgomery reduction. But the main purpose of this execution time comparison is to compare the ratio of the execution time of the proposed method with other well studied methods. The result shows that proposed method is at least 3 times faster than the other methods. Other acceleration techniques such as Montgomery reduction, Montgomery trick and efficient coordinates can be applied to this proposed method to enhance its execution time.

5 Conclusion and Future Work

In this paper we have proposed an efficient method to calculate elliptic curve scalar multiplication using Frobenious mapping over KSS curve in context of pairing based cryptography. We have also applied $(t-1)$-adic and z-adic representation on the scalar and have applied multi-scalar multiplication technique to calculate scalar multiplication in parallel. We have evaluated and analyzed the improvement by implementing a simulation for large size of scalar in 192-bit security level. The experimented result shows that our proposed method is at least 3 times efficient in context of execution time and takes 5 times less number of elliptic curve doubling than binary method, sliding-window method and non-adjacent form method. As a future work we would like to enhance its computation time by applying not only Montgomery reduction but also skew Frobenius map in sub-field isomorphic rational point group technique and test the effect of the improvement in some pairing application for practical case.