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
 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.
 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.
 S. Brands. Rethinking Public Key Infrastructures and Digital Certificates-
Building in Privacy. MIT Press, p.356, 2000.
 T. ElGamal. A Public key Cryptosystem and a Signature Scheme Based on
Discrete Logarithms. IEEE Transactions on Information Theory, vol.31,
 D. Hankerson, A. Menezes, and S. Vanstone. Guide to Elliptic Curve
Cryptography. Springer-Verlag, 2004.
 D. Knuth. Fundamental Algorithms. The Art of Computer Programming,
volume 1, Addision-Wesley, 1981.
 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.
 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.
 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.
 A.J. Menezes, P.C. vanOorschot, and S.A. Vanstone. Handbook of
Applied Cryptography. CRC Press, 1997.
 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.
 T. Okamoto. Practical identification schemes as secure as the DL and
RSA problems. http://grouper.
ieee.org/groups/1363/addendum.html#Okamoto, March 1999.
 N. Vorobiev. Fibonacci Numbers. Birkhuser Verlag, 2002.