Paper 2006/305

Provably Sublinear Point Multiplication on Koblitz Curves and its Hardware Implementation

V. S. Dimitrov, K. U. Jaervinen, M. J. Jacobson Jr., 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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. This is an extended version of our paper accepted to CHES 2006.
Keywords
elliptic curve cryptosystemsKoblitz curvespoint multiplicationdouble-base number systemshardware implementation
Contact author(s)
jacobs @ cpsc ucalgary ca
History
2006-09-07: revised
2006-09-06: received
See all versions
Short URL
https://ia.cr/2006/305
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/305,
      author = {V. S.  Dimitrov and K. U.  Jaervinen and M. J.  Jacobson Jr. and W. F.  Chan and Z.  Huang},
      title = {Provably Sublinear Point Multiplication on Koblitz Curves and its Hardware Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2006/305},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/305}},
      url = {https://eprint.iacr.org/2006/305}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.