Abstract
We present new algorithms computing 3P and \(2P+Q\) by removing the same part of numerators and denominators of their formulas, given two points P and Q on elliptic curves defined over prime fields and binary fields in affine coordinates. Our algorithms save one or two field multiplications compared with ones presented by Ciet, Joye, Lauter, and Montgomery. Since \(2P+Q\) takes \(\frac{1}{3}\) proportion, 28.5 % proportion, and 25.8 % proportion of all point operations by non-adjacent form, binary/ternary approach and tree approach to compute scalar multiplications respectively, 3P occupies 42.9 % proportion and 33.4 % proportion of all point operations by binary/ternary approach and tree approach to compute scalar multiplications respectively, utilizing our new formulas of \(2P+Q\) and 3P, scalar multiplications by using non-adjacent form, binary/ternary approach and tree approach are improved.
This research is supported in part by National Research Foundation of China under Grant No. 61379137, No. 61272040, and in part by National Basic Research Program of China(973) under Grant No.2013CB338001.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Longa, P., Gebotys, C.: Fast multibase methods and other several optimizations for elliptic curve scalar multiplication. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 443–462. Springer, Heidelberg (2009)
Longa, P., Miri, A.: Fast and flexible elliptic curve point arithmetic over prime fields. IEEE Trans. Comput. 57(3), 289–302 (2008)
Le, D.P., Nguyen, B.Pb.: Fast point quadupling on elliptic curve. In: SoICT 2012, pp. 218–222. ACM (2012)
Bernstein, D.J., Lange, T.: http://www.hyperelliptic.org/EFD/ (2015)
Reitwiesner, G.W.: Binary arithmetic. Adv. Comput. 1, 231–308 (1960)
Dimitrov, V.S., Imbert, L., Mishra, P.K.: Efficient and secure elliptic curve point multiplication using double-base chains. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 59–78. Springer, Heidelberg (2005)
Dimitrov, V.S., Imbert, L., Mishra, P.K.: The double-base number system and its application to elliptic curve cryptography. Math. Comp. 77(262), 1075–1104 (2008)
Doche, C., Habsieger, L.: A tree-based approach for computing double-base chains. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 433–446. Springer, Heidelberg (2008)
Méloni, N., Hasan, M.A.: Elliptic curve scalar multiplication combining Yao’s algorithm and double bases. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 304–316. Springer, Heidelberg (2009)
Méloni, N., Hasan, M.A.: Efficient double bases for scalar multiplication. IEEE Trans. Comput. PP(99), 1 (2015)
Doche, C.: On the enumeration of double-base chains with applications to elliptic curve cryptography. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 297–316. Springer, Heidelberg (2014)
Adikari, J., Dimitrov, V.S., Imbert, L.: Hybrid binary ternary number system for elliptic curve cryptosystems. IEEE Trans. Comput. 60, 254–265 (2011)
Doche, C., Sutantyo, D.: New and improved methods to analyze and compute double-scalar multiplications. IEEE Trans. Comput. 63(1), 230–242 (2014)
Ciet, M., Joye, M., Lauter, K., Montgomery, P.L.: Trading inversions for multiplications in elliptic curve cryptography. Des. Codes Crypt. 39(2), 189–206 (2006)
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)
Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005)
Eisenträger, K., Lauter, K., Montgomery, P.L.: Fast elliptic curve arithmetic and improved weil pairing evaluation. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 343–354. Springer, Heidelberg (2003)
Brown, M., Hankerson, D., López, J., Menezes, A.: Software implementation of the NIST elliptic curves over prime fields. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 250–265. Springer, Heidelberg (2001)
Dahmen, E., Okeya, K., Schepers, D.: Affine precomputation with sole inversion in elliptic curve cryptography. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 245–258. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Yu, W., Kim, K.H., Jo, M.S. (2015). New Fast Algorithms for Elliptic Curve Arithmetic in Affine Coordinates. In: Tanaka, K., Suga, Y. (eds) Advances in Information and Computer Security. IWSEC 2015. Lecture Notes in Computer Science(), vol 9241. Springer, Cham. https://doi.org/10.1007/978-3-319-22425-1_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-22425-1_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22424-4
Online ISBN: 978-3-319-22425-1
eBook Packages: Computer ScienceComputer Science (R0)