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

*Wei Yu and Saud Al Musa and 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.

**Category / Keywords: **Elliptic curve cryptography, Koblitz curve, Window $\tau$NAF, Pre-computation, Lambda coordinate

**Date: **received 14 Oct 2017, last revised 23 Oct 2017

**Contact author: **yuwei_1_yw at 163 com

**Available format(s): **PDF | BibTeX Citation

**Version: **20171025:025014 (All versions of this report)

**Short URL: **ia.cr/2017/1020

[ Cryptology ePrint archive ]