IJPAM: Volume 87, No. 1 (2013)

ANALYSIS ON THE ELLIPTIC SCALAR MULTIPLICATION
USING INTEGER SUB-DECOMPOSITION METHOD

Ruma Kareem K. Ajeena$^1$, Hailiza Kamarulhaili$^2$
$^{1,2}$School of Mathematical Sciences
University Sains Malaysia
11800 USM, Penang, MALAYSIA


Abstract. This study proposes a new approach called, integer sub-decomposition (ISD), to compute any multiple $kP$ of a point $P$ of order $n$ lying on an elliptic curve. Our method depends, in computations, on fast endomorphisms $\psi_{1}$ and $\psi_{2}$ of elliptic curve over prime fields. The integer sub-decomposition to multiple $kP$, when the value of $k$ is decomposed into two values $k_{1}$ and $k_{2}$, where both values or one of them is not bounded by $\pm\mathcal{C}~\sqrt{n}$, is illustrated in the following formula:
\begin{equation*} \begin{array}{c} \displaystyle{kP=k_{11}P+k_{12}[\lambda_{1}]P... ...11}P+k_{12}\psi_{1}(P)+k_{21}P+k_{22}\psi_{2}(P)}.\\ \end{array}\end{equation*}
where $-\mathcal{C}\sqrt{n}<k_{11},k_{12},k_{21},k_{22}<\mathcal{C}\sqrt{n}$. The integers $k_{11},k_{12},k_{21}$ and $k_{22}$ are computed by solving a closest vector problem in lattice. Consequently, as for this sub-decomposition, we have managed to increase the percentage of a successful computation of $kP$. Moreover, the gap in the proof of the bound of kernel $\mathcal{K}$ vectors of the reduction map $T:(a,b)\rightarrow a+\lambda b (mod~ n)$ on ISD method will be filled through the analysis of the multiplier $k$, using two fast endomorphisms with minimal polynomials $X^{2}+rX_{i}+s_{i}$ for $i=1,2,3$. In particular, we prove an integer sub-decomposition (ISD) with explicit constant

\begin{displaymath}kP= k_{11}P+k_{12}\psi_{1}(P)+k_{21}P+k_{22}\psi_{2}(P),\end{displaymath}

with

\begin{displaymath}max\{\vert k_{11}\vert,\vert k_{12}\vert\} ~~ \mbox{and} ~~ m... ...\sqrt{1+\vert r_{i}\vert+s_{i}}~\sqrt{n}~,~\mbox{for}~~i=1,2,3.\end{displaymath}



Received: May 3, 2013

AMS Subject Classification: 06-xx, 18B35, 06Bxx, 03G10

Key Words and Phrases: elliptic curves, fast performance, efficiently-computable endomorphisms, integer sub-decomposition

Download paper from here.


DOI: 10.12732/ijpam.v87i1.5 How to cite this paper?
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 87
Issue: 1