Abstract
We construct new families of elliptic curves over \(\mathbb{F}_{p^2}\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant–Lambert–Vanstone (GLV) and Galbraith–Lin–Scott (GLS) endomorphisms. Our construction is based on reducing quadratic ℚ-curves (curves defined over quadratic number fields, without complex multiplic’ation, but with isogenies to their Galois conjugates) modulo inert primes. As a first application of the general theory we construct, for every prime p > 3, two one-parameter families of elliptic curves over \(\mathbb{F}_{p^2}\) equipped with endomorphisms that are faster than doubling. Like GLS (which appears as a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding secure group orders when p is fixed. Unlike GLS, we also offer the possibility of constructing twist-secure curves. Among our examples are prime-order curves over \(\mathbb{F}_{p^2}\), equipped with fast endomorphisms, and with almost-prime-order twists, for the particularly efficient primes p = 2127 − 1 and p = 2255 − 19.
Chapter PDF
Similar content being viewed by others
References
Babai, L.: On Lovasz’ lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986)
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards Curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)
Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 194–210. Springer, Heidelberg (2013)
Bosma, W., Cannon, J.J., Fieker, C., Steel (eds.): Handbook of Magma functions, 2.19 edn. (2013)
Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. Chapman & Hall / CRC (2006)
Doche, C., Icart, T., Kohel, D.R.: Efficient scalar multiplication by isogeny decompositions. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 191–206. Springer, Heidelberg (2006)
Elkies, N.D.: On elliptic k-curves. In: Cremona, J., Lario, J.-C., Quer, J., Ribet, K. (eds.) Modular Curves and Abelian Varieties, pp. 81–92. Birkhäuser, Basel (2004)
Ellenberg, J.S.: ℚ-curves and Galois representations. In: Cremona, J., Lario, J.-C., Quer, J., Ribet, K. (eds.) Modular Curves and Abelian Varieties, pp. 93–103. Birkhäuser, Basel (2004)
Fouque, P.-A., Lercier, R., Réal, D., Valette, F.: Fault attack on elliptic curve with Montgomery ladder. In: FDTC 2008, pp. 92–98. IEEE-CS (2008)
Galbraith, S.D.: Mathematics of public key cryptography. Cambridge University Press (2012)
Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Crypt. 24(3), 446–469 (2011)
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190–200. Springer, Heidelberg (2001)
González, J.: Isogenies of polyquadratic ℚ-curves to their Galois conjugates. Arch. Math. 77, 383–390 (2001)
Guillevic, A., Ionica, S.: Four-dimensional GLV via the Weil restriction. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013 Part I. LNCS, vol. 8269, pp. 79–96. Springer, Heidelberg (2013)
Hasegawa, Y.: ℚ-curves over quadratic fields. Manuscripta Math. 94(1), 347–364 (1997)
Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008)
Kohel, D.R., Smith, B.A.: Efficiently computable endomorphisms for hyperelliptic curves. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 495–509. Springer, Heidelberg (2006)
Longa, P., Sica, F.: Four-dimensional Gallant–Lambert–Vanstone scalar multiplication. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 718–739. Springer, Heidelberg (2012), http://eprint.iacr.org/2011/608
The Magma computational algebra system, http://magma.maths.usyd.edu.au
Montgomery, P.L.: Speeding the Pollard and Elliptic Curve Methods of factorization. Math. Comp. 48(177), 243–264 (1987)
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory 39(5), 1639–1646 (1993)
Okeya, K., Kurumatani, H., Sakurai, K.: Elliptic curves with the Montgomery-form and their cryptographic applications. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 238–257. Springer, Heidelberg (2000)
Quer, J.: Fields of definition of ℚ-curves. J. Théor. Nombres Bordeaux 13(1), 275–285 (2001)
Quer, J.: ℚ-curves and abelian varieties of GL2-type. Proc. London Math. 81(2), 285–317 (2000)
Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44, 735–763 (1985)
Sica, F., Ciet, M., Quisquater, J.J.: Analysis of the Gallant-Lambert-Vanstone Method Based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 21–36. Springer, Heidelberg (2003)
Silverman, J.H.: The arithmetic of elliptic curves. Grad. Texts in Math. 106(2e) (2009)
Straus, E.G.: Addition chains of vectors. Amer. Math. Monthly 71(7), 806–808 (1964)
Takashima, K.: A new type of fast endomorphisms on Jacobians of hyperelliptic curves and their cryptographic application. IEICE Trans. Fundamentals E89-A(1), 124–133 (2006)
Vélu, J.: Isogénies entre courbes elliptiques. C. R. Math. Acad. Sci. Paris 273, 238–241 (1971)
Verheul, E.: Evidence that XTR is more secure than supersingular elliptic curve cryptosystems. J. Crypt. 17, 277–296 (2004)
Zhou, Z., Hu, Z., Xu, M., Song, W.: Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves. Inf. Proc. Lett. 110(22), 1003–1006 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Smith, B. (2013). Families of Fast Elliptic Curves from ℚ-curves. In: Sako, K., Sarkar, P. (eds) Advances in Cryptology - ASIACRYPT 2013. ASIACRYPT 2013. Lecture Notes in Computer Science, vol 8269. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-42033-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-42033-7_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-42032-0
Online ISBN: 978-3-642-42033-7
eBook Packages: Computer ScienceComputer Science (R0)