**Provably Sublinear Point Multiplication on Koblitz Curves and its Hardware Implementation**

*V.S. Dimitrov and K.U. Jaervinen and M.J. Jacobson Jr. and W.F. Chan and Z. Huang*

**Abstract: **We describe algorithms for point multiplication on Koblitz curves
using multiple-base expansions of the form $k = \sum \pm \tau^a
(\tau-1)^b$ and $k= \sum \pm \tau^a (\tau-1)^b (\tau^2 - \tau - 1)^c.$
We prove that the number of terms in the second type is sublinear in
the bit length of k, which leads to the first provably sublinear point
multiplication algorithm on Koblitz curves. For the first type, we
conjecture that the number of terms is sublinear and provide
numerical evidence demonstrating that the number of terms is
significantly less than that of $\tau$-adic non-adjacent form
expansions. We present details of an innovative FPGA
implementation of our algorithm and performance data demonstrating the
efficiency of our method.

**Category / Keywords: **public-key cryptography / elliptic curve cryptosystems, Koblitz curves, point multiplication, double-base number systems, hardware implementation

**Publication Info: **This is an extended version of our paper accepted to CHES 2006.

**Date: **received 5 Sep 2006, last revised 7 Sep 2006

**Contact author: **jacobs at cpsc ucalgary ca

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20060907:172138 (All versions of this report)

**Short URL: **ia.cr/2006/305

[ Cryptology ePrint archive ]