Abstract
Isogenies are widely used in elliptic curves. Since Moody and Shumow [20] proposed isogenies on Edwards and Huff curves analogues of Vélu’s formulas, they have pointed out a new way to construct isogenies. However, hardly any isogeny on Jacobi quartic curves has been designed, this paper extends their work to construct isogenies on extended Jacobi quartic curves for the first time including a 2-isogeny and a generalized l-isogeny for any odd l as well as an improved l-isogeny. This paper also estimates the time complexity of the improved l-isogeny. If the constants are carefully chosen, the Jacobi quartic isogeny is about to catch up with Huff isogeny.
This work is supported in part by National Research Foundation of China under Grant No. 61502487, 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(177), 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). doi:10.1007/3-540-39799-X_31
Brier, E., Joye, M.: Fast point multiplication on elliptic curves through isogenies. In: Fossorier, M., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 43–50. Springer, Heidelberg (2003). doi:10.1007/3-540-44828-4_6
Tate, J.: Endomorphisms of abelian varieties over finite field. Ivent. Math. 2(2), 134–144 (1966)
Schoof, R.: Elliptic curves over finite field and the computation of square roots mod p. Math. Comp. 44(170), 483–494 (1985)
Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. J. Comput. Math. 2, 118–138 (1999)
Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptology 15(1), 19–46 (2002)
Galbraith, S., Stolbunov, A.: Improved algorithm for the isogeny problem for ordinary elliptic curves. Appl. Algebra Eng. Commun. Comput. 24(2), 107–131 (2013)
Biasse, J.-F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 428–442. Springer, Cham (2014). doi:10.1007/978-3-319-13039-2_25
Jao, D., Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25405-5_2
Billet, O., Joye, M.: The jacobi model of an elliptic curve and side-channel analysis. In: Fossorier, M., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 34–42. Springer, Heidelberg (2003). doi:10.1007/3-540-44828-4_5
Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Jacobi quartic curves revisited. In: Boyd, C., González Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 452–468. Springer, Heidelberg (2009). doi:10.1007/978-3-642-02620-1_31
Duquesne, S.: Improving the arithmetic of elliptic curves in the Jacobi model. Inf. Process. Lett. 104(3), 101–105 (2007)
Hisil, H., Carter, G., Dawson, E.: New formulae for efficient elliptic curve arithmetic. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 138–151. Springer, Heidelberg (2007). doi:10.1007/978-3-540-77026-8_11
Hisil, H., Wong, K.K.H., Carter, G., Dawson, E.: Faster group operations on elliptic curves. AISC 2009, vol. 98, pp. 7–20 (2009)
Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518–535. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01001-9_30
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). doi:10.1007/3-540-44647-8_11
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). doi:10.1007/11745853_13
Moody, D.: Using 5-isogenies to quintuple points on elliptic curves. Inf. Process. Lett. 111, 314–317 (2011)
Moody, D., Shumow, D.: Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves. Math. Comp. 85(300), 1929–1951 (2016)
Vélu, J.: Isogénied entre courbes elliptiques. C.R. Acad. Sc. Paris Série A. 273, 238–241 (1971)
Kohel, D.: Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California at Berkeley (1996)
Hisil, H.: Elliptic curves, group law, and efficient computation. PhD thesis, Queensland University of Technology (2010)
Moody, D.: Divison polynomials for alternate models of elliptic curves. IACR Cryptology ePrint Archive 2010, 630 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Xu, X., Yu, W., Wang, K., He, X. (2017). Constructing Isogenies on Extended Jacobi Quartic Curves. In: Chen, K., Lin, D., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2016. Lecture Notes in Computer Science(), vol 10143. Springer, Cham. https://doi.org/10.1007/978-3-319-54705-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-54705-3_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-54704-6
Online ISBN: 978-3-319-54705-3
eBook Packages: Computer ScienceComputer Science (R0)