Cryptology ePrint Archive: Report 2017/1020

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:

[ Cryptology ePrint archive ]