### New Multibase Non-Adjacent Form Scalar Multiplication and its Application to Elliptic Curve Cryptosystems (extended version)

Patrick Longa and Ali Miri

##### Abstract

In this paper we present a new method for scalar multiplication that uses a generic multibase representation to reduce the number of required operations. Further, a multibase NAF-like algorithm that efficiently converts numbers to such representation without impacting memory or speed performance is developed and showed to be sublinear in terms of the number of nonzero terms. Additional representation reductions are discussed with the introduction of window-based variants that use an extended set of precomputations. To realize the proposed multibase scalar multiplication with or without precomputations in the setting of Elliptic Curve Cryptosystems (ECC) over prime fields, we also present a methodology to derive fast composite operations such as tripling or quintupling of a point that require less memory than previous point formulae. Point operations are then protected against simple side-channel attacks using a highly efficient atomic structure. Extensive testing is carried out to show that our multibase scalar multiplication is the fastest method to date in the setting of ECC and exhibits a small footprint, which makes it ideal for implementation on constrained devices.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
multibase non-adjacent form (mbNAF)composite operationsscalar multiplicationelliptic curve cryptosystemside-channel attacks
Contact author(s)
plonga @ uwaterloo ca
History
2008-03-14: last of 2 revisions
See all versions
Short URL
https://ia.cr/2008/052

CC BY

BibTeX

@misc{cryptoeprint:2008/052,
author = {Patrick Longa and Ali Miri},
title = {New Multibase Non-Adjacent Form Scalar Multiplication and its Application to Elliptic Curve Cryptosystems (extended version)},
howpublished = {Cryptology ePrint Archive, Paper 2008/052},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/052}},
url = {https://eprint.iacr.org/2008/052}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.