Paper 2008/285

Hybrid Binary-Ternary Joint Sparse Form and its Application in Elliptic Curve Cryptography

Jithra Adikari, Vassil Dimitrov, and Laurent Imbert

Abstract

Multi-exponentiation is a common and time consuming operation in public-key cryptography. Its elliptic curve counterpart, called multi-scalar multiplication is extensively used for digital signature verification. Several algorithms have been proposed to speed-up those critical computations. They are based on simultaneously recoding a set of integers in order to minimize the number of general multiplications or point additions. When signed-digit recoding techniques can be used, as in the world of elliptic curves, Joint Sparse Form (JSF) and interleaving $w$-NAF are the most efficient algorithms. In this paper, a novel recoding algorithm for a pair of integers is proposed, based on a decomposition that mixes powers of 2 and powers of 3. The so-called Hybrid Binary-Ternary Joint Sparse Form require fewer digits and is sparser than the JSF and the interleaving $w$-NAF. Its advantages are illustrated for elliptic curve double-scalar multiplication; the operation counts show a gain of up to 18\%.

Note: Major correction in the theoretical analysis

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multi-exponentiationMulti-scalar multiplicationJoint sparse formBinary-ternary number systemElliptic curves.
Contact author(s)
jithra adikari @ atips ca
History
2008-07-03: revised
2008-07-03: received
See all versions
Short URL
https://ia.cr/2008/285
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/285,
      author = {Jithra Adikari and Vassil Dimitrov and Laurent Imbert},
      title = {Hybrid Binary-Ternary Joint Sparse Form and its Application in Elliptic Curve Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2008/285},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/285}},
      url = {https://eprint.iacr.org/2008/285}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.