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+ax^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\bar{\tau}$-operations in lambda coordinates ($\mu=(-1)^{1-a}$ and $\bar{\tau}$ is the complex conjugate of the complex representation of $\tau$). Efficient formulas of $\mu\bar{\tau}$-operations are then derived and used in a novel pre-computation scheme to improve the efficiency of scalar multiplications using window $\tau$NAF. Our pre-computation scheme costs $7$M$+5$S, $26$M$+16$S, and $66$M$+36$S for window $\tau$NAF with width $4$, $5$, and $6$ respectively whereas the pre-computation with the state-of-the-art technique costs $11$M$+8$S, $43$M$+18$S, and $107$M$+36$S. Experimental results show that our pre-computation is about $60\%$ faster, compared to the best pre-computation in the literature. It also shows that we can save from $2.5\%$ to $4.9\%$ on the scalar multiplications using window $\tau$NAF with our pre-computation.