Cryptology ePrint Archive: Report 2006/305

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 formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

Discussion forum: Show discussion | Start new discussion