Commenced in January 2007
Paper Count: 31100
Novel Method for Elliptic Curve Multi-Scalar Multiplication
Abstract: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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058497Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1295
 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, pp.469-472, 1985.
 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. Springer-Verlag, 1993.
 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.