Paper 2017/1020

A Novel Pre-Computation Scheme of Window $\tau$NAF for Koblitz Curves

Wei Yu, Saud Al Musa, Guangwu Xu, and Bao Li

Abstract

Let $E_a:y^2+xy=x^3+a{x}^2+1/{\mathbb{F}}_{2^m}$ be a Koblitz curve. The window $\tau$-adic nonadjacent-form (window $\tau$NAF) is currently the standard representation system to perform scalar multiplications on $E_a$ by utilizing the Frobenius map $\tau$. Pre-computation is an important part for the window $\tau$NAF. In this paper, we first introduce $\mu \overline{\tau }$-operations in lambda coordinates ($\mu =(-1{)}^{1-a}$ and $\overline{\tau }$ is the complex conjugate of the complex representation of $$). Efficient formulas of $$-operations are then derived and used in a novel pre-computation scheme to improve the efficiency of scalar multiplications using window $$NAF. Our pre-computation scheme costs $$M$$S, $$M$$S, and $$M$$S for window $$NAF with width $$, $$, and $$ respectively whereas the pre-computation with the state-of-the-art technique costs $$M$$S, $$M$$S, and $$M$$S. Experimental results show that our pre-computation is about $$ faster, compared to the best pre-computation in the literature. It also shows that we can save from $$ to $$ on the scalar multiplications using window $$NAF with our pre-computation.