Paper 2008/051

New Composite Operations and Precomputation Scheme for Elliptic Curve Cryptosystems over Prime Fields (full version)

Patrick Longa and Ali Miri

Abstract

We present a new methodology to derive faster composite operations of the form dP+Q, where d is a small integer >= 2, for generic ECC scalar multiplications over prime fields. In particular, we present an efficient Doubling-Addition (DA) operation that can be exploited to accelerate most scalar multiplication methods, including multiscalar variants. We also present a new precomputation scheme useful for window-based scalar multiplications that is shown to achieve the lowest cost among all known methods using only one inversion. In comparison to the remaining approaches that use none or several inversions, our scheme offers higher performance for most common I/M ratios. By combining the benefits of our precomputation scheme and the new DA operation, we can save up to 6.2% in the scalar multiplication using fractional wNAF.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. The short version will appear in PKC2008.
Keywords
Elliptic curve cryptosystem
Contact author(s)
plonga @ uwaterloo ca
History
2008-01-31: received
Short URL
https://ia.cr/2008/051
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/051,
      author = {Patrick Longa and Ali Miri},
      title = {New Composite Operations and Precomputation Scheme for Elliptic Curve Cryptosystems over Prime Fields (full version)},
      howpublished = {Cryptology ePrint Archive, Paper 2008/051},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/051}},
      url = {https://eprint.iacr.org/2008/051}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.