Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Dustin Moody and Daniel Shumow
Journal: Math. Comp. 85 (2016), 1929-1951
MSC (2010): Primary 14K02; Secondary 14H52, 11G05, 11Y16
DOI: https://doi.org/10.1090/mcom/3036
Published electronically: September 9, 2015
MathSciNet review: 3471114
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1016/j.jnt.2011.12.013
  • [2] 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 (2010e:11057), https://doi.org/10.1007/978-3-540-68164-9_26
  • [3] 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 (2011d:11125), https://doi.org/10.1007/978-3-540-76900-2_3
  • [4] 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 (2012a:11080), https://doi.org/10.1016/j.jnt.2009.11.003
  • [5] 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 (2009k:11207), https://doi.org/10.1090/S0025-5718-08-02066-8
  • [6] 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 (2012i:94143), https://doi.org/10.1007/978-3-540-85538-5_7
  • [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 (2012m:11180), https://doi.org/10.1090/S0025-5718-2011-02508-1
  • [8] 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 (2010d:94074), https://doi.org/10.1007/s00145-007-9002-x
  • [9] 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.
  • [10] L. De Feo, Algorithmes rapides pour les tours de corps finis et les isogenies, PhD thesis. Ecole Polytechnique X, (2010).
  • [11] 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 (2009m:94045), https://doi.org/10.1007/11745853_13
  • [12] Harold M. Edwards, A normal form for elliptic curves, Bull. Amer. Math. Soc. (N.S.) 44 (2007), no. 3, 393-422 (electronic). MR 2318157 (2008b:14052), https://doi.org/10.1090/S0273-0979-07-01153-6
  • [13] 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 (99a:11078)
  • [14] 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.
  • [15] 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, https://doi.org/10.1016/j.ffa.2011.12.004
  • [16] 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 (2010m:11069), https://doi.org/10.1007/s10623-009-9310-2
  • [17] 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.
  • [18] 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 (2005c:11077), https://doi.org/10.1007/3-540-45455-1_23
  • [19] L. Hitt, G. Mcguire, and R. Moloney, Division polynomials for twisted Edwards curves, Preprint, (2008). Available at http://arxiv.org/pdf/0907.4347v1.pdf.
  • [20] Gerald B. Huff, Diophantine problems in geometry and elliptic ternary forms, Duke Math. J. 15 (1948), 443-453. MR 0025489 (10,14c)
  • [21] 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, https://doi.org/10.1007/978-3-642-25405-5_2
  • [22] 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 (2007e:94060), https://doi.org/10.1007/11593447_2
  • [23] 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 (2011h:11144), https://doi.org/10.1007/978-3-642-14518-6_19
  • [24] 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 (2011g:11236), https://doi.org/10.1007/978-3-642-14518-6_20
  • [25] 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, https://doi.org/10.1007/s00200-011-0153-5
  • [26] 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
  • [27] 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 (99a:11079)
  • [28] Dustin Moody, Using 5-isogenies to quintuple points on elliptic curves, Inform. Process. Lett. 111 (2011), no. 7, 314-317. MR 2790157 (2011m:11117), https://doi.org/10.1016/j.ipl.2010.12.014
  • [29] 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.
  • [30] D. Shumow, Isogenies of elliptic curves: A computational approach, Masters Thesis, University of Washington, (2009).
  • [31] Joseph H. Silverman, The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210 (87g:11070)
  • [32] 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 (86e:11122), https://doi.org/10.2307/2007968
  • [33] 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 (2011k:94108), https://doi.org/10.3934/amc.2010.4.215
  • [34] Andrew V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp. 80 (2011), no. 273, 501-538. MR 2728992 (2011k:11177), https://doi.org/10.1090/S0025-5718-2010-02373-7
  • [35] Edlyn Teske, An elliptic curve trapdoor system, J. Cryptology 19 (2006), no. 1, 115-133. MR 2210901 (2006k:94116), https://doi.org/10.1007/s00145-004-0328-3
  • [36] Jacques Vélu, Isogénies entre courbes elliptiques, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A238-A241 (French). MR 0294345 (45 #3414)
  • [37] Lawrence C. Washington, Elliptic Curves, (Number Theory and Cryptography), 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2008. MR 2404461 (2009b:11101)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14K02, 14H52, 11G05, 11Y16

Retrieve articles in all journals with MSC (2010): 14K02, 14H52, 11G05, 11Y16


Additional Information

Dustin Moody
Affiliation: Computer Security Division, National Institute of Standards and Technology (NIST), Gaithersburg, Maryland 20899
Email: dustin.moody@nist.gov

Daniel Shumow
Affiliation: Microsoft Research, Redmond, Washington 98052-6399
Email: danshu@microsoft.com

DOI: https://doi.org/10.1090/mcom/3036
Keywords: Elliptic curve, Edwards curve, Huff curve
Received by editor(s): December 16, 2013
Received by editor(s) in revised form: July 10, 2014, and December 23, 2014
Published electronically: September 9, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society