Novel Method for Elliptic Curve Multi-Scalar Multiplication

The major building block of most elliptic curve cryptosystems are computation of multi-scalar multiplication. This paper proposes a novel algorithm for simultaneous multi-scalar multiplication, that is by employing addition chains. The previously known methods utilizes double-and-add algorithm with binary representations. In order to accomplish our purpose, an efficient empirical method for finding addition chains for multi-exponents has been proposed.

Authors:

• Raveen R. Goundar
• Ken-ichi Shiota
• Masahiko Toyonaga

Keywords:

• elliptic curve cryptosystems
• multi-scalar multiplication
• addition chains
• Fibonacci sequence.

References:

[1] R.M. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F.
Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography.
CRC Press, 2005.
[2] M. Bellare, J.A. Garray, and T. Rabin. Fast Batch verification for
modular exponentiation and digital signatures. Advances in Cryptology-
EUROCRYPTO-98, volume 1403 of Lecture Notes in Computing Science,
pages 236-250. Springer-Verlag, 1998.
[3] S. Brands. Rethinking Public Key Infrastructures and Digital Certificates-
Building in Privacy. MIT Press, p.356, 2000.
[4] T. ElGamal. A Public key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms. IEEE Transactions on Information Theory, vol.31,
pp.469-472, 1985.
[5] D. Hankerson, A. Menezes, and S. Vanstone. Guide to Elliptic Curve
Cryptography. Springer-Verlag, 2004.
[6] D. Knuth. Fundamental Algorithms. The Art of Computer Programming,
volume 1, Addision-Wesley, 1981.
[7] K. Kobayashi, H. Morita, and M. Hakuta. Multiple Scalar-Multiplication
Algorithm over Elliptic Curve. IEICE Transactions on Information and
System, E84-D, No.2, pp.271-276, Feb.2001.
[8] C.H. Lim and P.J. Lee. More Flexible Exponentiation with Precomputation.
Advances in Cryptology-CRYPTO-94, volume 839 of Lecture Notes
in Computing Science, pages 95-107. Springer-Verlag, 1994.
[9] B. M¨oller. Algorithms for Multi-exponentiation. Selected Areas in Cryptography,
volume 2259 of Lecture Notes in Computing Science, pages
165-180. Springer-Verglag, 2001.
[10] A.J. Menezes, P.C. vanOorschot, and S.A. Vanstone. Handbook of
Applied Cryptography. CRC Press, 1997.
[11] T. Okamoto. Provably secure and practical identification schemes and
corresponding signature schemes. Advances in Cryptology-CRYPTO-92,
volume 740 of Lecture Notes in Computing Science, pages 31-53.
Springer-Verlag, 1993.
[12] T. Okamoto. Practical identification schemes as secure as the DL and
RSA problems. http://grouper.
ieee.org/groups/1363/addendum.html#Okamoto, March 1999.
[13] N. Vorobiev. Fibonacci Numbers. Birkhuser Verlag, 2002.