Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves

Moody, Dustin; Shumow, Daniel

doi:10.1090/mcom/3036

Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves
HTML articles powered by AMS MathViewer

by Dustin Moody and Daniel Shumow PDF

Math. Comp. 85 (2016), 1929-1951 Request permission

Abstract:

Isogenies are the morphisms between elliptic curves and are, accordingly, a topic of interest in the subject. As such, they have been well studied, and have been used in several cryptographic applications. Vélu’s formulas show how to explicitly evaluate an isogeny, given a specification of the kernel as a list of points. However, Vélu’s formulas only work for elliptic curves specified by a Weierstrass equation. This paper presents formulas similar to Vélu’s that can be used to evaluate isogenies on Edwards curves and Huff curves, which are normal forms of elliptic curves that provide an alternative to the traditional Weierstrass form. Our formulas are not simply compositions of Vélu’s formulas with mappings to and from Weierstrass form. Our alternate derivation yields efficient formulas for isogenies with lower algebraic complexity than such compositions. In fact, these formulas have lower algebraic complexity than Vélu’s formulas on Weierstrass curves.

References

Omran Ahmadi and Robert Granger, On isogeny classes of Edwards curves over finite fields, J. Number Theory 132 (2012), no. 6, 1337–1358. MR 2899808, DOI 10.1016/j.jnt.2011.12.013
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters, Twisted Edwards curves, Progress in cryptology—AFRICACRYPT 2008, Lecture Notes in Comput. Sci., vol. 5023, Springer, Berlin, 2008, pp. 389–405. MR 2482341, DOI 10.1007/978-3-540-68164-9_{2}6
Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on elliptic curves, Advances in cryptology—ASIACRYPT 2007, Lecture Notes in Comput. Sci., vol. 4833, Springer, Berlin, 2007, pp. 29–50. MR 2565722, DOI 10.1007/978-3-540-76900-2_{3}
Gaetan Bisson and Andrew V. Sutherland, Computing the endomorphism ring of an ordinary elliptic curve over a finite field, J. Number Theory 131 (2011), no. 5, 815–831. MR 2772473, DOI 10.1016/j.jnt.2009.11.003
A. Bostan, F. Morain, B. Salvy, and É. Schost, Fast algorithms for computing isogenies between elliptic curves, Math. Comp. 77 (2008), no. 263, 1755–1778. MR 2398793, DOI 10.1090/S0025-5718-08-02066-8
Reinier Bröker, Denis Charles, and Kristin Lauter, Evaluating large degree isogenies and applications to pairing based cryptography, Pairing-based cryptography—Pairing 2008, Lecture Notes in Comput. Sci., vol. 5209, Springer, Berlin, 2008, pp. 100–112. MR 2733907, DOI 10.1007/978-3-540-85538-5_{7}
Reinier Bröker, Kristin Lauter, and Andrew V. Sutherland, Modular polynomials via isogeny volcanoes, Math. Comp. 81 (2012), no. 278, 1201–1231. MR 2869057, DOI 10.1090/S0025-5718-2011-02508-1
Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptology 22 (2009), no. 1, 93–113. MR 2496385, DOI 10.1007/s00145-007-9002-x
H. Debiao, C. Jianhua, and H. Jin, A random number generator based on isogenies operations, Cryptology ePrint Archive Report 2010/94, (2010). Available at http://eprint.iacr.org/2010/094.
L. De Feo, Algorithmes rapides pour les tours de corps finis et les isogenies, PhD thesis. Ecole Polytechnique X, (2010).
Christophe Doche, Thomas Icart, and David R. Kohel, Efficient scalar multiplication by isogeny decompositions, Public key cryptography—PKC 2006, Lecture Notes in Comput. Sci., vol. 3958, Springer, Berlin, 2006, pp. 191–206. MR 2423190, DOI 10.1007/11745853_{1}3
Harold M. Edwards, A normal form for elliptic curves, Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 3, 393–422. MR 2318157, DOI 10.1090/S0273-0979-07-01153-6
Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21–76. MR 1486831, DOI 10.1090/amsip/007/03
R. Farashahi, On the number of distinct Legendre, Jacobi, Hessian and Edwards curves (Extended Abstract), in: Proceedings of the Workshop on Coding theory and Cryptology (WCC 2011), pp. 37–46, (2011). Available at hal.inria.fr/docs/00/60/72/79/PDF/76.pdf.
Reza Rezaeian Farashahi, Dustin Moody, and Hongfeng Wu, Isomorphism classes of Edwards curves over finite fields, Finite Fields Appl. 18 (2012), no. 3, 597–612. MR 2899901, DOI 10.1016/j.ffa.2011.12.004
Reza Rezaeian Farashahi and Igor E. Shparlinski, On the number of distinct elliptic curves in some families, Des. Codes Cryptogr. 54 (2010), no. 1, 83–99. MR 2576882, DOI 10.1007/s10623-009-9310-2
R. Feng, and H. Wu, Elliptic curves in Huff’s model, Cryptology ePrint Archive Report 2010/390, (2010). Available at http://eprint.iacr.org/2010/390.pdf.
Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 276–291. MR 2041091, DOI 10.1007/3-540-45455-1_{2}3
L. Hitt, G. Mcguire, and R. Moloney, Division polynomials for twisted Edwards curves, Preprint, (2008). Available at http://arxiv.org/pdf/0907.4347v1.pdf.
Gerald B. Huff, Diophantine problems in geometry and elliptic ternary forms, Duke Math. J. 15 (1948), 443–453. MR 25489
David Jao and Luca De Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-quantum cryptography, Lecture Notes in Comput. Sci., vol. 7071, Springer, Heidelberg, 2011, pp. 19–34. MR 2931459, DOI 10.1007/978-3-642-25405-5_{2}
David Jao, Stephen D. Miller, and Ramarathnam Venkatesan, Do all elliptic curves of the same order have the same difficulty of discrete log?, Advances in cryptology—ASIACRYPT 2005, Lecture Notes in Comput. Sci., vol. 3788, Springer, Berlin, 2005, pp. 21–40. MR 2236725, DOI 10.1007/11593447_{2}
David Jao and Vladimir Soukharev, A subexponential algorithm for evaluating large degree isogenies, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 219–233. MR 2721423, DOI 10.1007/978-3-642-14518-6_{1}9
Marc Joye, Mehdi Tibouchi, and Damien Vergnaud, Huff’s model for elliptic curves, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 234–250. MR 2721424, DOI 10.1007/978-3-642-14518-6_{2}0
Richard Moloney and Gary McGuire, Two kinds of division polynomials for twisted Edwards curves, Appl. Algebra Engrg. Comm. Comput. 22 (2011), no. 5-6, 321–345. MR 2863388, DOI 10.1007/s00200-011-0153-5
David Russell Kohel, Endomorphism rings of elliptic curves over finite fields, ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)–University of California, Berkeley. MR 2695524
R. Lercier and F. Morain, Algorithms for computing isogenies between elliptic curves, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 77–96. MR 1486832, DOI 10.1090/amsip/007/04
Dustin Moody, Using 5-isogenies to quintuple points on elliptic curves, Inform. Process. Lett. 111 (2011), no. 7, 314–317. MR 2790157, DOI 10.1016/j.ipl.2010.12.014
A. Rostovtsev and A. Stolbunov, Public-key cryptosystem based on isogenies, Cryptology ePrint Archive, Report 2006/145, (2006). Available at http://eprint.iacr.org/2006/145.
D. Shumow, Isogenies of elliptic curves: A computational approach, Masters Thesis, University of Washington, (2009).
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
Anton Stolbunov, Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, Adv. Math. Commun. 4 (2010), no. 2, 215–235. MR 2654134, DOI 10.3934/amc.2010.4.215
Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501–538. MR 2728992, DOI 10.1090/S0025-5718-2010-02373-7
Edlyn Teske, An elliptic curve trapdoor system, J. Cryptology 19 (2006), no. 1, 115–133. MR 2210901, DOI 10.1007/s00145-004-0328-3
Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238–A241 (French). MR 294345
Lawrence C. Washington, Elliptic curves, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. Number theory and cryptography. MR 2404461, DOI 10.1201/9781420071474