Endomorphisms for faster elliptic curve cryptography on a large class of curves. (English) Zbl 1258.94036

Summary: Efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the Gallant-Lambert-Vanstone (GLV) method. T. Iijima et al. (2002) gave such homomorphisms for a large class of elliptic curves by working over \(\mathbb{F}_{p^2}\). We extend their results and demonstrate that they can be applied to the GLV method.
In general we expect our method to require about \(0.75\) the time of previous best methods (except for subfield curves, for which Frobenius expansions can be used). We give detailed implementation results which show that the method runs in between \(0.70\) and \(0.83\) the time of the previous best methods for elliptic curve point multiplication on general curves.


94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
14G50 Applications to coding theory and cryptography of arithmetic geometry
Full Text: DOI


[1] Antipa, A.; Brown, D. R.L.; Gallant, R. P.; Lambert, R. J.; Struik, R.; Vanstone, S. A.; Preneel, B.; Tavares, S. E., Accelerated verification of ecdsa signatures, SAC 2005, 307-318 (2006), Berlin: Springer, Berlin · Zbl 1151.94595
[2] Avanzi, R.; Joye, M.; Quisquater, J.-J., Aspects of hyperelliptic curves over large prime fields in software implementations, CHES 2004, 148-162 (2004), Berlin: Springer, Berlin · Zbl 1104.68463
[3] Avanzi, R.; Cohen, H.; Doche, C.; Frey, G.; Lange, T.; Nguyen, K.; Vercauteren, F., Handbook of Elliptic and Hyperelliptic Curve Cryptography (2006), London, Boca Raton: Chapman and Hall/CRC, London, Boca Raton · Zbl 1082.94001
[4] Bernstein, D. J.; Yung, M., Curve25519: new Diffie-Hellman speed records, PKC 2006, 207-228 (2006), Berlin: Springer, Berlin · Zbl 1151.94480
[5] D.J. Bernstein, Differential addition chains, preprint (2006). http://cr.yp.to/papers.html#diffchain
[6] D.J. Bernstein, Elliptic vs. hyperelliptic, part 1 ECC 2006, Toronto, Canada. http://www.cacr.math.uwaterloo.ca/conferences/2006/ecc2006/slides.html
[7] Bernstein, D. J.; Lange, T.; Kurosawa, K., Faster addition and doubling on elliptic curves, Asiacrypt 2007, 29-50 (2007), Berlin: Springer, Berlin · Zbl 1153.11342
[8] Bernstein, D. J.; Lange, T.; Boztas, S.; Lu, H.-F., Inverted Edwards coordinates, AAECC 2007, 20-27 (2007), Berlin: Springer, Berlin · Zbl 1195.14047
[9] Bernstein, D. J.; Lange, T., Analysis and optimization of elliptic-curve single-scalar multiplication, Finite Fields and Applications: Proceedings of Fq8, 1-18 (2008), Providence: Am. Math. Soc., Providence · Zbl 1184.94225
[10] Bernstein, D. J.; Birkner, P.; Joye, M.; Lange, T.; Peters, C.; Vaudenay, S., Twisted Edwards curves, Africacrypt 2008, 389-405 (2008), Berlin: Springer, Berlin · Zbl 1142.94332
[11] Blake, I.; Seroussi, G.; Smart, N. P., Elliptic Curves in Cryptography (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0937.94008
[12] eBATS: ECRYPT benchmarking of asymmetric systems, http://www.ecrypt.eu.org/ebats/
[13] D.J. Bernstein, T. Lange (eds.), eBACS: ECRYPT benchmarking of cryptographic systems, http://bench.cr.yp.to/, accessed 9 January 2009
[14] D.R.L. Brown, Multi-dimensional Montgomery ladders for elliptic curves, eprint 2006/220. http://www.eprint.iacr.org/2006/220
[15] Dahmen, E.; Okeya, K.; Schepers, D.; Pieprzyk, J.; Ghodosi, H.; Dawson, E., Affine precomputation with sole inversion in elliptic curve cryptography, ACISP 2007, 245-258 (2007), Berlin: Springer, Berlin · Zbl 1213.94096
[16] Duursma, I. M.; Gaudry, P.; Morain, F.; Lam, K.-Y.; Okamoto, E.; Xing, C., Speeding up the discrete log computation on curves with automorphisms, ASIACRYPT 1999, 103-121 (1999), Berlin: Springer, Berlin · Zbl 0968.14034
[17] Edwards, H. M., A normal form for elliptic curves, Bull. Am. Math. Soc., 44, 393-422 (2007) · Zbl 1134.14308 · doi:10.1090/S0273-0979-07-01153-6
[18] Galbraith, S. D.; Scott, M.; Galbraith, S. D.; Paterson, K. G., Exponentiation in pairing-friendly groups using homomorphisms, Pairing 2008, 211-224 (2008), Berlin: Springer, Berlin · Zbl 1186.94441
[19] Galbraith, S. D.; Lin, X.; Scott, M.; Joux, A., Endomorphisms for faster elliptic curve cryptography on a large class of curves, EUROCRYPT 2009, 518-535 (2009), Berlin: Springer, Berlin · Zbl 1239.94048
[20] Gallant, R. P.; Lambert, R. J.; Vanstone, S. A., Improving the parallelized Pollard lambda search on anomalous binary curves, Math. Comput., 69, 1699-1705 (2000) · Zbl 1101.14325
[21] Gallant, R. P.; Lambert, R. J.; Vanstone, S. A.; Kilian, J., Faster point multiplication on elliptic curves with efficient endomorphisms, CRYPTO 2001, 190-200 (2001), Berlin: Springer, Berlin · Zbl 1002.94022
[22] Gaudry, P., Index calculus for Abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symb. Comput., 44, 12, 1690-1702 (2009) · Zbl 1177.94148 · doi:10.1016/j.jsc.2008.08.005
[23] P. Gaudry, E. Thomé, The mpFq library and implementing curve-based key exchanges, SPEED workshop presentation, Amsterdam, June 2007. www.hyperelliptic.org/SPEED/record.pdf
[24] Gaudry, P.; Thomé, E.; Thériault, N.; Diem, C., A double large prime variation for small genus hyperelliptic index calculus, Math. Comput., 76, 257, 475-492 (2007) · Zbl 1179.94062 · doi:10.1090/S0025-5718-06-01900-4
[25] P. Gaudry, E. Schost, Hyperelliptic curve point counting record: 254 bit Jacobian, post to NMBRTHRY list, 22 Jun 2008. http://www.loria.fr/gaudry/record127/
[26] R. Granger, On the static Diffie-Hellman problem on elliptic curves over extension fields, eprint 2010/177 · Zbl 1290.94079
[27] Hankerson, D.; Menezes, A. J.; Vanstone, S., Guide to Elliptic Curve Cryptography (2004), Berlin: Springer, Berlin · Zbl 1059.94016
[28] Hankerson, D.; Karabina, K.; Menezes, A. J., Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields, IEEE Trans. Comput., 58, 10, 1411-1420 (2009) · Zbl 1367.94314 · doi:10.1109/TC.2009.61
[29] Hess, F.; Smart, N.; Vercauteren, F., The eta-pairing revisited, IEEE Trans. Inf. Theory, 52, 10, 4595-4602 (2006) · Zbl 1189.11057 · doi:10.1109/TIT.2006.881709
[30] T. Iijima, K. Matsuo, J. Chao, S. Tsujii, Construction of Frobenius maps of twist elliptic curves and its application to elliptic scalar multiplication, in SCIS 2002, IEICE Japan, January 2002, pp. 699-702
[31] Kim, D.; Lim, S.; Nyberg, K.; Heys, H., Integer decomposition for fast scalar multiplication on elliptic curves, SAC 2002, 13-20 (2003), Berlin: Springer, Berlin · Zbl 1125.94325
[32] Kozaki, S.; Matsuo, K.; Shimbara, Y., Skew-Frobenius maps on hyperelliptic curves, IEICE Trans., E91-A, 7, 1839-1843 (2008) · doi:10.1093/ietfec/e91-a.7.1839
[33] Longa, P.; Miri, A.; Cramer, R., New composite operations and precomputation scheme for elliptic curve cryptosystems over prime fields, PKC 2008, 229-247 (2008), Berlin: Springer, Berlin · Zbl 1162.94387
[34] Möller, B.; Vaudenay, S.; Youssef, A. M., Algorithms for multi-exponentiation, SAC 2001, 165-180 (2001), Berlin: Springer, Berlin · Zbl 1067.94554
[35] Möller, B.; Lee, P.; Lim, C., Improved techniques for fast exponentiation, ICISC 2002, 298-312 (2003), Berlin: Springer, Berlin · Zbl 1030.11075
[36] Möller, B.; Park, C.; Chee, S., Fractional windows revisited: improved signed-digit representations for efficient exponentiation, ICISC 2004, 137-153 (2005), Berlin: Springer, Berlin · Zbl 1133.94328
[37] Möller, B.; Rupp, A.; Ostrovsky, R.; De Prisco, R.; Visconti, I., Faster multi-exponentiation through caching: accelerating (EC)DSA signature verification, SCN 2008, 39-56 (2008), Berlin: Springer, Berlin · Zbl 1180.68153
[38] Montgomery, P. L., Speeding the Pollard and elliptic curve methods of factorization, Math. Comput., 47, 243-264 (1987) · Zbl 0608.10005
[39] Y. Nogami, Y. Morikawa, Fast generation of elliptic curves with prime order over extension field of even extension degree, in Proceedings 2003 IEEE International Symposium on Information Theory (2003), p. 18
[40] Y. Nogami, Y. Morikawa, Fast generation of elliptic curves with prime order over \({\mathbb{F}}_{p^{2^c}} \). Workshop on Coding and Cryptography (WCC2003) (2003), pp. 347-356
[41] Park, Y.-H.; Jeong, S.; Kim, C. H.; Lim, J.; Naccache, D.; Paillier, P., An alternate decomposition of an integer for faster point multiplication on certain elliptic curves, PKC 2002, 323-334 (2002), Berlin: Springer, Berlin · Zbl 1055.94527
[42] Rostovtsev, A. G.; Markovenko, E. B.; Gorodetsky, V., Elliptic curve point multiplication, MMM-ACNS 2003, 328-336 (2003), Berlin: Springer, Berlin
[43] Schmidt-Samoa, K.; Semay, O.; Takagi, T., analysis of fractional window recoding methods and their application to elliptic curve cryptosystems, IEEE Trans. Comput., 55, 1, 48-57 (2006) · Zbl 1294.94077 · doi:10.1109/TC.2006.3
[44] M. Scott, MIRACL—multiprecision integer and rational arithmetic C/C++ library, http://ftp.computing.dcu.ie/pub/crypto/miracl.zip (2008)
[45] M. Scott, P. Szczechowiak, Optimizing multiprecision multiplication for public key cryptography, eprint 2007/299. http://eprint.iacr.org/2007/299
[46] Sica, F.; Ciet, M.; Quisquater, J.-J.; Nyberg, K.; Heys, H. M., Analysis of the Gallant-Lambert-Vanstone method based on efficient endomorphisms: elliptic and hyperelliptic curves, SAC 2002, 21-36 (2003), Berlin: Springer, Berlin · Zbl 1066.94551
[47] Silverman, J. H., The Arithmetic of Elliptic Curves (1986), Berlin: Springer, Berlin · Zbl 0585.14026
[48] Solinas, J. A., Efficient arithmetic on Koblitz curves, Designs Codes and Cryptogr., 19, 2-3, 195-249 (2000) · Zbl 0997.94017 · doi:10.1023/A:1008306223194
[49] J.A. Solinas, Low-weight binary representations for pairs of integers. Technical Report CORR 2001-41, CACR (2001)
[50] Wiener, M. J.; Zuccherato, R. J.; Tavares, S.; Meijer, H., Faster attacks on elliptic curve cryptosystems, SAC 1998, 190-200 (1999), Berlin: Springer, Berlin · Zbl 1025.94511
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.