Abstract
Scalar multiplication is the most expensive arithmetical operation on elliptic curves. There are various methods available, which are optimized for different settings, such as high speed, side-channel resistance and small memory footprint. One of the fastest methods for fixed-base scalar multiplications is the so-called fixed-base comb scalar multiplication method, which is due to Lim and Lee. In this paper, we present a modification to this method, which exploits the possibility of exchanging doublings for much cheaper applications of the Frobenius endomorphism on binary Koblitz curves. We have implemented the findings in software and compare the performance of the implementation to the performance of the reference WTNAF implementation and the performance of the conventional comb multiplication methods. For single scalar multiplications, we are able to achieve performance improvements over the WTNAF method of up to 25% and of up to 42% over the conventional comb methods. Finally, we emphasize that the implementation of the τ-comb method is straight-forward and requires only little effort. All in all, this makes it a good alternative to other fixed-base multiplication methods.
Chapter PDF
Similar content being viewed by others
Keywords
References
Aranha, D.F., Faz-Hernández, A., López, J., Rodríguez-Henríquez, F.: Faster implementation of scalar multiplication on Koblitz curves. In: Hevia, A., Neven, G. (eds.) LatinCrypt 2012. LNCS, vol. 7533, pp. 177–193. Springer, Heidelberg (2012)
Avanzi, R.M., Ciet, M., Sica, F.: Faster scalar multiplication on Koblitz curves combining point halving with the Frobenius endomorphism. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 28–40. Springer, Heidelberg (2004), http://www.iacr.org/cryptodb/archive/2004/PKC/3329/3329.pdf
Avanzi, R.M., Heuberger, C., Prodinger, H.: Minimality of the hamming weight of the τ-NAF for koblitz curves and improved combination with point halving. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 332–344. Springer, Heidelberg (2006)
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press (2005)
Gallagher, P., Furlani, C.: FIPS PUB 186-3 federal information processing standards publication digital signature standard, dss (2009)
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer-Verlag New York, Inc., Secaucus (2003)
Higuchi, A., Takagi, N.: A fast addition algorithm for elliptic curve arithmetic in GF(2n) using projective coordinates. Inf. Process. Lett. 76(3), 101–103 (2000)
Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), 203–209 (1987)
Lange, T.: A note on López-Dahab coordinates. IACR Cryptology ePrint Archive 2004, 323 (2004)
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2n). In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 201–212. Springer, Heidelberg (1999)
López, J., Dahab, R.: High-speed software multiplication in \({F}_{2^m}\). In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 203–212. Springer, Heidelberg (2000)
Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. In: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 80–89. ACM, New York (1991)
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)
Mohamed, N.A.F., Hashim, M.H.A., Hutter, M.: Improved fixed-base comb method for fast scalar multiplication. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 342–359. Springer, Heidelberg (2012)
Schroeppel, R., Orman, H., O’Malley, S., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 43–56. Springer, Heidelberg (1995)
Silverman, J.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106. Springer (1986)
Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Codes Cryptography 19(2/3), 195–249 (2000)
Tsaur, W.J., Chou, C.H.: Efficient algorithms for speeding up the computations of elliptic curve cryptosystems. Applied Mathematics and Computation 168(2), 1045–1064 (2005), http://www.sciencedirect.com/science/article/pii/S0096300304006629
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 IFIP International Federation for Information Processing
About this paper
Cite this paper
Hanser, C., Wagner, C. (2013). Speeding Up the Fixed-Base Comb Method for Faster Scalar Multiplication on Koblitz Curves. In: Cuzzocrea, A., Kittl, C., Simos, D.E., Weippl, E., Xu, L. (eds) Security Engineering and Intelligence Informatics. CD-ARES 2013. Lecture Notes in Computer Science, vol 8128. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40588-4_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-40588-4_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40587-7
Online ISBN: 978-3-642-40588-4
eBook Packages: Computer ScienceComputer Science (R0)