IACR paper details
Title  Provably Sublinear Point Multiplication on Koblitz Curves and its Hardware Implementation 

Booktitle  IACR Eprint archive 

Pages  

Year  2006 

URL  http://eprint.iacr.org/2006/305 

Author  V.S. Dimitrov 

Author  K.U. Jaervinen 

Author  M.J. Jacobson 

Author  W.F. Chan 

Author  Z. Huang 

Abstract 
We describe algorithms for point multiplication on Koblitz curves
using multiplebase expansions of the form $k = \sum \pm \tau^a
(\tau1)^b$ and $k= \sum \pm \tau^a (\tau1)^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 nonadjacent form
expansions. We present details of an innovative FPGA
implementation of our algorithm and performance data demonstrating the
efficiency of our method.


Search for the paper
@misc{eprint200621796,
title={Provably Sublinear Point Multiplication on Koblitz Curves and its Hardware Implementation},
booktitle={IACR Eprint archive},
keywords={publickey cryptography / elliptic curve cryptosystems, Koblitz curves, point multiplication, doublebase number systems, hardware implementation},
url={http://eprint.iacr.org/2006/305},
note={This is an extended version of our paper accepted to CHES 2006. jacobs@cpsc.ucalgary.ca 13398 received 5 Sep 2006, last revised 7 Sep 2006},
author={V.S. Dimitrov and K.U. Jaervinen and M.J. Jacobson and W.F. Chan and Z. Huang},
year=2006
}
Download a complete BibTeX file.