Evaluating Composite EC Operations and their Applicability to the on-the-fly and non-window Multiplication Methods

Abstract

In order to improve the efficiency of elliptic curve multiplication methods, extended and composite elliptic curve operations such as nP,mP+Q, where n>2and m?2, and repeated doublings were proposed. These operations have lower complexity, in terms of field operations, than that for classical methods. Moreover, they are supposed to replace the classical methods. In this paper, repeated doublings and odd point computation are deeply analyzed in order to measure their actual efficiency. According to the gained results, the improvement ratio in the execution time is not the same as the improvement ratio measured in terms of field operations. Moreover, different implementations of Sakai repeated doubling method yield different results. For example, implementing 4P as a separate function gives lower complexity than implementing repeated doublings as a general function. On the other hand, other methods for computing nP, where n is odd, have been analyzed. Dahmen method failed to meet the expected results for computing odd points in elliptic curve multiplication methods that employ the on-the-fly strategy since its time complexity was more than that for classical methods. It was also found that new techniques should be devised to improve the efficiency of window methods for calculating odd points such as: 5P, 7P, and 15P, which have lower cost than that for classical method.

References

• H. Darrel, J. M. Alfred, and V. Scott, Guide to Elliptic Curve Cryptography: Springer-Verlag New York, Inc. , 2003.
• W. Stallings, "Cryptography and Network Security: Principles and Practice," 2013.
• J. A. Solinas, "low-weight binary representations for pairs of integers," 2001.
• K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi, "Signed binary representations revisited," Proceedings of CRYPTO'04, vol. 3152, pp. 123-139, 2004.
• K. W. Wong, E. C. W. Lee, L. M. Cheng, and X. Liao, "Fast elliptic scalar multiplication using new double-base chain and point halving," Applied Mathematics and Computation, vol. 183, pp. 1000-1007, Dec 15 2006.
• V. S. Dimitrov, G. A. Jullien, and W. C. Miller, "An algorithm for modular exponentiation," Information Processing Letters, 66, 155-159, 1998.
• M. Ciet, M. Joye, K. Lauter, and P. L. Montgomery, "Trading inversions for multiplications in elliptic curve cryptography," Designs Codes and Cryptography, vol. 39, pp. 189-206, May 2006.
• Y. Sakai and K. Sakurai, "Efficient scalar multiplications on elliptic curves with direct computations of several doublings," IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, vol. E84a, pp. 120-129, Jan 2001.
• E. Dahmen, K. Okeya, and D. Schepers, "Affine precomputation with sole inversion in elliptic curve cryptography," in Information Security and Privacy, Proceedings. vol. vol. 4586, ed, 2007, pp. pp. 245-258.
• K. Eisenträger, K. Lauter, and P. L. Montgomery, "Fast elliptic curve arithmetic and improved Weil pairing evaluation," Topics in Cryptology, Lecture Notes in Computer Science, vol. 2612, pp. 343-354, 2003.
• H. Darrel, L. Julio, H. pez, and M. Alfred, "Software Implementation of Elliptic Curve Cryptography over Binary Fields," Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, pp. 1-24, 2000.
• V. Dimitrov, L. Imbert, and P. K. Mishra, "Efficient and secure elliptic curve point multiplication using double-base chains," Advances in Cryptology Asiacrypt 2005, 3788, 59-78, 2005.
• M. Brown, D. Hankerson, J. Lopez, and A. Menezes, "Software implementation of the NIST elliptic curves over prime fields," Topics in Cryptology, vol. 2020, pp. 250-265, 2001.
• P. Gallagher, D. D. Foreword, and C. F. Director, "FIPS PUB 186-3 Federal Information Processing Standards Publication Digital Signature Standard (DSS)," 2009.
• D. E. Knuth, The art of computer programming, 3rd ed. vol. 2. Boston, MA, USA: Addison-Wesley Longman Publishing Co. , Inc. , 1997.
• K. Fong, D. Hankerson, J. López, and A. Menezes, "Field inversion and point halving revisited," IEEE Transactions on Computers, vol. 53, pp. 1047-1059, Aug 2004.
• J. Guajardo and C. Paar, "Efficient algorithms for elliptic curve cryptosystems," Advances in Cryptology - Crypto'97, Proceedings, vol. 1294, pp. 342-356, 1997.
• N. Koblitz, "Constructing Elliptic Curve Cryptosystems in Characteristic . 2," CRYPTO '90 Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, vol. 537, pp. 156-167, 1991.
• A. J. Menezes, S. A. Vanstone, and R. J. Zuccherato, "Counting Points on Elliptic Curves Over F2m," Mathematics of Computation, vol. 60, pp. 407-420, 1993.
• V. Muller, "Efficient algorithms for multiplication on elliptic curves " in Chipkarten, P. Horster, Ed. , ed TU Munchen: Vieweg+Teubner Verlag, 1998, pp. pp. 135-145.
• A. Miyaji, T. Ono, and H. Cohen, "Efficient elliptic curve exponentiation," ICICS '97: Proceedings of the First International Conference on Information and Communication Security, vol. 1334, pp. 282-290, 1997.
• H. Cohen and G. Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography: Chapman & Hall/CRC, 2006.
• Shamus. (2010, December 16). MIRACL Library. Available: http://www. shamus. ie/
• A. Abusharekh and K. Gaj, "Comparative Analysis of Software Libraries for Public Key Cryptography," in Software Performance Enhancement for Encryption and Decryption, Amsterdam, 2007, pp. pp. 3 - 19.
• K. Koyama and Y. Tsuruoka, "Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method," Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, pp. 345-357, 1993.
• F. Morain and J. Olivos, "Speeding up the Computations on an Elliptic Curve Using Addition-Subtraction Chains," Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications, vol. 24, pp. 531-544, 1990.

Index Terms

Keywords