International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jithra Adikari
Vassil Dimitrov
Laurent Imbert
Download:
URL: http://eprint.iacr.org/2008/285
Search ePrint
Search Google
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\%.
BibTeX
@misc{eprint-2008-17962,
  title={Hybrid Binary-Ternary Joint Sparse Form and its Application in Elliptic Curve Cryptography},
  booktitle={IACR Eprint archive},
  keywords={Multi-exponentiation, Multi-scalar multiplication, Joint sparse form, Binary-ternary number system, Elliptic curves.},
  url={http://eprint.iacr.org/2008/285},
  note={ jithra.adikari@atips.ca 14063 received 25 Jun 2008, last revised 3 Jul 2008},
  author={Jithra Adikari and Vassil Dimitrov and Laurent Imbert},
  year=2008
}