Paper 2018/964

Fast Scalar Multiplication for Elliptic Curves over Prime Fields by Efficiently Computable Formulas

Saud Al Musa and Guangwu Xu

Abstract

This paper addresses fast scalar multiplication for elliptic curves over finite fields. In the first part of the paper, we obtain several efficiently computable formulas for basic elliptic curves arithmetic in the family of twisted Edwards curves over prime fields. Our $2Q+P$ formula saves about $2.8$ field multiplications, and our $5P$ formula saves about $4.2$ field multiplications in standard projective coordinate systems, compared to the latest existing results. In the second part of the paper, we formulate bucket methods for the DAG-based and the tree-based abstract ideas. We propose systematically finding a near optimal chain for multi-base number systems (MBNS). These proposed bucket methods take significantly less time to find a near optimal chain, compared to an optimal chain. We conducted extensive experiments to compare the performance of the MBNS methods (e.g., greedy, ternary/binary, multi-base NAF, tree-based, rDAG-based, and bucket). Our proposed formulas were integrated in these methods. Our results show our work had an important role in advancing the efficiency of scalar multiplication.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
twisted Edwards curvesEdwards curvesscalar multiplicationefficient formulasDBNSMBNS
Contact author(s)
gxu4uwm @ uwm edu
History
2018-10-18: revised
2018-10-14: received
See all versions
Short URL
https://ia.cr/2018/964
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/964,
      author = {Saud Al Musa and Guangwu Xu},
      title = {Fast Scalar Multiplication for Elliptic Curves over Prime Fields by Efficiently Computable Formulas},
      howpublished = {Cryptology ePrint Archive, Paper 2018/964},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/964}},
      url = {https://eprint.iacr.org/2018/964}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.