International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Scalar Multiplication on Koblitz Curves using Double Bases

Authors:
Roberto Maria Avanzi
Francesco Sica
Download:
URL: http://eprint.iacr.org/2006/067
Search ePrint
Search Google
Abstract: The paper is an examination of double-base decompositions of integers $n$, namely expansions loosely of the form $$ n = \sum_{i,j} A^iB^j $$ for some base $\{A,B\}$. This was examined in previous works in the case when $A,B$ lie in $\mathbb{N}$. On the positive side, we show how to extend previous results of to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer $n$ and an elliptic curve point $P$, the point $nP$ in time $O\left(\frac{\log n}{\log\log n}\right)$ elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. On the negative side, we analyze scalar multiplication using double base numbers and show that on a generic elliptic curve over a finite field, we cannot expect a sublinear algorithm with double bases. Finally, we show that all algorithms used hitherto need at least $\frac{\log n}{\log\log n}$ curve operations.
BibTeX
@misc{eprint-2006-21560,
  title={Scalar Multiplication on Koblitz Curves using Double Bases},
  booktitle={IACR Eprint archive},
  keywords={implementation / elliptic curve cryptosystem, fast endomorphisms, number theory},
  url={http://eprint.iacr.org/2006/067},
  note={ fsica@mta.ca 13200 received 21 Feb 2006},
  author={Roberto Maria Avanzi and Francesco Sica},
  year=2006
}