International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Setting Speed Records with the (Fractional) Multibase Non-Adjacent Form Method for Efficient Elliptic Curve Scalar Multiplication

Authors:
Catherine Gebotys
Patrick Longa
Download:
URL: http://eprint.iacr.org/2008/118
Search ePrint
Search Google
Abstract: In this paper, we introduce the Fractional Window-w Multibase Non-Adjacent Form (Frac-wmbNAF) method to perform the scalar multiplication. This method generalizes the recently developed Window-w mbNAF (wmbNAF) method by allowing an unrestricted number of precomputed points. We then make a comprehensive analysis of the most recent and relevant methods existent in the literature for the ECC scalar multiplication, including the presented generalization and its original non-window version known as Multibase Non-Adjacent Form (mbNAF). Moreover, we present new improvements in the point operation formulae. Specifically, we reduce further the cost of composite operations such as doubling-addition, tripling, quintupling and septupling of a point, which are relevant for the speed up of methods using multiple bases. Following, we also analyze the precomputation stage in scalar multiplications and present efficient schemes for the different studied scenarios. Our analysis includes the standard elliptic curves using Jacobian coordinates, and also Edwards curves, which are gaining growing attention due to their high performance. We demonstrate with extensive tests that mbNAF is currently the most efficient method without precomputations not only for the standard curves but also for the faster Edwards form. Similarly, Frac-wmbNAF is shown to attain the highest performance among window-based methods for all the studied curve forms.
BibTeX
@misc{eprint-2008-17795,
  title={Setting Speed Records with the (Fractional) Multibase Non-Adjacent Form Method for Efficient Elliptic Curve Scalar Multiplication},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Elliptic curve cryptosystem, scalar multiplication, multibase non-adjacent form, fractional windows, point operation, composite operation, precomputation scheme.},
  url={http://eprint.iacr.org/2008/118},
  note={CACR technical report (University of Waterloo) plonga@uwaterloo.ca 13954 received 16 Mar 2008},
  author={Catherine Gebotys and Patrick Longa},
  year=2008
}