Malaysian Journal of Mathematical Sciences, June 2015, Vol. 9(S)
Special Issue: The 4th International Cryptology and Information Security Conference 2014 (Cryptology 2014)
Pseudo $\tau$-Adic Non Adjacent Form for Scalar Multiplication on Koblitz Curves
Faridah Yunos, Kamel Ariffin Mohd Atan, Muhammad Rezal Kamel Ariffin and Mohamad Rushdan Md Said
Corresponding Email: [email protected]
Received date: -
Accepted date: -
Abstract:
In ECC, scalar multiplication is the dominant operation, namely computing $nP$ from a point $P$ on an elliptic curve where the multiplier $n$ is an integer, defined as the point resulting from adding $P+P+...+P$, $n$ times. The $\tau$-NAF proposed by Solinas, is one of the most efficient algorithms to compute scalar multiplications on Koblitz curves. In this paper, we introduced an equivalent multiplier to $\tau$-NAF namely pseudoTNAF. It is based on the idea of transforming the $\tau$-NAF expression to a reduced $\tau$-NAF that has been done by some researchers. It can eliminate the elliptic doublings in scalar multiplication method, and double the number of elliptic additions. We provide the formula for obtaining a total of lattice points in Voronoi region of modulo $r+s \tau$ where $r+s \tau$ an element of ring $Z(\tau)$. This helps us to find all the multipliers $n$ that based on $\tau$-NAF. We also discuss the estimation of operational costs when using pseudoTNAF as a multiplier of scalar multiplication
Keywords: multiplication, Koblitz curve, density, Voronoi region, Hamming weight
