Malaysian Journal of Mathematical Sciences, June 2015, Vol. 9(S)
Special Issue: The 4th International Cryptology and Information Security Conference 2014 (Cryptology 2014)
Accelerating Integer Sub-Decomposition for Elliptic Scalar Multiplication using the Generalized $w_j$-NAF Expansions Method
Ruma Kareem K. Ajeena and Hailiza Kamarulhaili
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
In this paper, wNAF expansion method is used to compute a scalar multiplication on classes of elliptic curve over a prime field that have efficiently-computable endomorphisms. This scalar multiplication is called integer sub-decomposition (ISD) method, which is based on the GLV method of Gallant, Lambert and Vanstone that was initially proposed in the year 2001. In this work the ISD implementation uses speed parallel computation of endomorphisms $\psi_i$ for $i = 1,2$ to compute the multiple $kP$ of a point $P$ of order n lying on an elliptic curve. The decomposition of a scalar k according to GLV method produces two integers $k_1$ and $k_2$ lie inside the range of $\pm \sqrt{N}$. This decomposition also gives significant number of integers $k_1$ and $k_2$ lie outside the given range of $\pm \sqrt{N}$. These outliers are not considered in the GLV method. Therefore, the ISD approach is proposed to bridge the gap and to complement the GLV method. Besides that, the ISD method helps increase the percentage of successful computation of $kP$. In this paper, the main idea is to present the parallel computation of ISD elliptic scalar multiplication which is defined by the following decompositions
$$kP= k_{11}P+ k_{12} \psi_{1}(P)+ k_{21}P+ k_{22} \psi_{2}(P)$$ with $\left | k_{11} \right |$, $\left | k_{12} \right |$, $\left | k_{21} \right |$, $\left | k_{22} \right | < \sqrt{N}$.
This computation employs two models using the interleaving methods based on parallel computation of the generalized $w_j$-NAF expansions for $j=1,2,3,4$. It is known that the parallel processing on two proposed interleaving methods produce more computation speed in comparison with the computations that were performed individually.
Keywords: Elliptic curve cryptography, Scalar multiplication, Parallel interleaving method, Parallel $w_j$-NAF expansions, Efficiently-computable endomorphisms, Integer sub-decomposition
