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

Patrick Longa; Catherine Gebotys

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2008/118

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

Patrick Longa and Catherine Gebotys

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. CACR technical report (University of Waterloo)
Keywords: Elliptic curve cryptosystem scalar multiplication multibase non-adjacent form fractional windows point operation composite operation precomputation scheme.
Contact author(s): plonga @ uwaterloo ca
History: 2008-03-17: received
Short URL: https://ia.cr/2008/118
License: CC BY

BibTeX

@misc{cryptoeprint:2008/118,
      author = {Patrick Longa and Catherine Gebotys},
      title = {Setting Speed Records with the (Fractional) Multibase Non-Adjacent Form Method for Efficient Elliptic Curve Scalar Multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2008/118},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/118}},
      url = {https://eprint.iacr.org/2008/118}
}