Computing (ℓ,ℓ)-isogenies in polynomial time on Jacobians of genus 2 curves

Cosset, Romain; Robert, Damien

doi:10.1090/S0025-5718-2014-02899-8

Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves
HTML articles powered by AMS MathViewer

by Romain Cosset and Damien Robert PDF

Math. Comp. 84 (2015), 1953-1975 Request permission

Abstract:

In this paper, we compute $\ell$-isogenies between abelian varieties over a field of characteristic different from $2$ in polynomial time in $\ell$, when $\ell$ is an odd prime which is coprime to the characteristic. We use level $n$ symmetric theta structure where $n=2$ or $n=4$. In the second part of this paper we explain how to convert between Mumford coordinates of Jacobians of genus $2$ hyperelliptic curves to theta coordinates of level $2$ or $4$. Combined with the preceding algorithm, this gives a method to compute $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves.

References

A.O.L. Atkin, The number of points on an elliptic curve modulo a prime, manuscript, Chicago IL, 1988.
Christina Birkenhake and Herbert Lange, Complex abelian varieties, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 302, Springer-Verlag, Berlin, 2004. MR 2062673, DOI 10.1007/978-3-662-06307-1
G. Bisson and A.V. Sutherland, Computing the endomorphism ring of an ordinary elliptic curve over a finite field, Journal of Number Theory, 2009.
Dan Boneh and Matthew Franklin, Identity-based encryption from the Weil pairing, SIAM J. Comput. 32 (2003), no. 3, 586–615. MR 2001745, DOI 10.1137/S0097539701398521
Dan Boneh, Ben Lynn, and Hovav Shacham, Short signatures from the Weil pairing, J. Cryptology 17 (2004), no. 4, 297–319. MR 2090559, DOI 10.1007/s00145-004-0314-9
Reinier Bröker, David Gruenewald, and Kristin Lauter, Explicit CM theory for level 2-structures on abelian surfaces, Algebra Number Theory 5 (2011), no. 4, 495–528. MR 2870099, DOI 10.2140/ant.2011.5.495
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
R. Dupont, Moyenne arithmético-géométrique, suites de Borchardt et applications. Ph.D. thesis, École polytechnique, 2006.
N.D. Elkies, Explicit isogenies, manuscript, Boston MA, 1992.
Andreas Enge, Pierrick Gaudry, and Emmanuel Thomé, An $L(1/3)$ discrete logarithm algorithm for low degree curves, J. Cryptology 24 (2011), no. 1, 24–41. MR 2755161, DOI 10.1007/s00145-010-9057-y
Jean-Charles Faugère, David Lubicz, and Damien Robert, Computing modular correspondences for abelian varieties, J. Algebra 343 (2011), 248–277. MR 2824556, DOI 10.1016/j.jalgebra.2011.06.031
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
P. Gaudry, Fast genus 2 arithmetic based on theta functions, J. Math. Cryptol. 1 (2007), no. 3, 243–265. MR 2372155, DOI 10.1515/JMC.2007.012
Pierrick Gaudry, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symbolic Comput. 44 (2009), no. 12, 1690–1702. MR 2553574, DOI 10.1016/j.jsc.2008.08.005
V. Goyal, O. Pandey, A. Sahai, and B. Waters, Attribute-based encryption for fine-grained access control of encrypted data, In Proceedings of the 13th ACM conference on Computer and communications security, page 98. ACM, 2006.
Jun-ichi Igusa, Theta functions, Die Grundlehren der mathematischen Wissenschaften, Band 194, Springer-Verlag, New York-Heidelberg, 1972. MR 0325625
Antoine Joux, A one round protocol for tripartite Diffie-Hellman, J. Cryptology 17 (2004), no. 4, 263–276. MR 2090557, DOI 10.1007/s00145-004-0312-y
George R. Kempf, Linear systems on abelian varieties, Amer. J. Math. 111 (1989), no. 1, 65–94. MR 980300, DOI 10.2307/2374480
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-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
Shoji Koizumi, Theta relations and projective normality of Abelian varieties, Amer. J. Math. 98 (1976), no. 4, 865–889. MR 480543, DOI 10.2307/2374034
David Lubicz and Damien Robert, Efficient pairing computation with theta functions, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 251–269. MR 2721425, DOI 10.1007/978-3-642-14518-6_{2}1
David Lubicz and Damien Robert, Computing isogenies between abelian varieties, Compos. Math. 148 (2012), no. 5, 1483–1515. MR 2982438, DOI 10.1112/S0010437X12000243
A. Menezes, T. Okamoto, and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, In Proceedings of the twenty-third annual ACM symposium on Theory of computing, page 89. ACM, 1991.
Jean-François Mestre, Construction de courbes de genre $2$ à partir de leurs modules, Effective methods in algebraic geometry (Castiglioncello, 1990) Progr. Math., vol. 94, Birkhäuser Boston, Boston, MA, 1991, pp. 313–334 (French). MR 1106431
D. Mumford, On the equations defining abelian varieties. I, Invent. Math. 1 (1966), 287–354. MR 204427, DOI 10.1007/BF01389737
D. Mumford, On the equations defining abelian varieties. II, Invent. Math. 3 (1967), 75–135. MR 219541, DOI 10.1007/BF01389741
D. Mumford, On the equations defining abelian varieties. III, Invent. Math. 3 (1967), 215–244. MR 219542, DOI 10.1007/BF01425401
David Mumford, Tata lectures on theta. II, Modern Birkhäuser Classics, Birkhäuser Boston, Inc., Boston, MA, 2007. Jacobian theta functions and differential equations; With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura; Reprint of the 1984 original. MR 2307768, DOI 10.1007/978-0-8176-4578-6
David Mumford, Tata lectures on theta. II, Progress in Mathematics, vol. 43, Birkhäuser Boston, Inc., Boston, MA, 1984. Jacobian theta functions and differential equations; With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. MR 742776, DOI 10.1007/978-0-8176-4578-6
David Mumford, The red book of varieties and schemes, Second, expanded edition, Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1999. Includes the Michigan lectures (1974) on curves and their Jacobians; With contributions by Enrico Arbarello. MR 1748380, DOI 10.1007/b62130
F. Richelot, Essai sur une méthode générale pour déterminer la valeur des intégrales ultra-elliptiques, fondée sur des transformations remarquables de ces transcendantes, C. R. Acad. Sci. Paris, 2:622–627, 1836.
F. Richelot, De transformatione Integralium Abelianorum primiordinis commentation, J. Reine Angew. Math., 16:221–341, 1837.
D. Robert, Theta functions and applications in cryptography. Ph.D. thesis, Université Henri-Poincaré, Nancy 1, France, July 2010.
Amit Sahai and Brent Waters, Fuzzy identity-based encryption, Advances in cryptology—EUROCRYPT 2005, Lecture Notes in Comput. Sci., vol. 3494, Springer, Berlin, 2005, pp. 457–473. MR 2352204, DOI 10.1007/11426639_{2}7
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
René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578
Benjamin Smith, Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves, J. Cryptology 22 (2009), no. 4, 505–529. MR 2525710, DOI 10.1007/s00145-009-9038-1
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
Paul van Wamelen, Equations for the Jacobian of a hyperelliptic curve, Trans. Amer. Math. Soc. 350 (1998), no. 8, 3083–3106. MR 1432144, DOI 10.1090/S0002-9947-98-02056-X
Eric R. Verheul, Self-blindable credential certificates from the Weil pairing, Advances in cryptology—ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, pp. 533–551. MR 1934862, DOI 10.1007/3-540-45682-1_{3}1