I‑AIMS Institute for Artificial Intelligence
and Mathematical Sciences
/

Curves, Jacobians, and cryptography

Gerhard Frey, Tanush Shaska

I-AIMS paper 2018-1 · Published in Contemp. Math. 724 (2019), 279–344 · 2019

The main purpose of this paper is to give the latest developments in the theory of abelian varieties and their usage in cryptography. In the first part we provide the necessary mathematical background on abelian varieties, their torsion points, Honda-Tate theory, Galois representations, with emphasis on Jacobian varieties and hyperelliptic Jacobians. In the second part we focus on applications of abelian varieties on cryptography and treating separately, elliptic curve cryptography, hyperelliptic curve cryptography for genus 2 and 3, and isogenies of Jacobians via correspondences. Many open problems are suggested through the paper.

MSC classes: Primary 14H40; Secondary 14H10, 14H45, 94A60

PDF

References

  1. L. Beshaj, Minimal weierstrass equations for genus 2 curves (2016), available at 1612.08318.
  2. L. Beshaj and S. Guest, Weighted projective space of binary sextics, 2018.
  3. Reinier Bröker, Everett W. Howe, Kristin E. Lauter, and Peter Stevenhagen, Genus-2 curves and jacobians with a given number of points (2014), available at 1403.6911.
  4. Reinier Bröker and Kristin Lauter, Modular polynomials for genus 2, LMS J. Comput. Math. 12 (2009), 326–339.
  5. David G. Cantor, On the analogue of the division polynomials for hyperelliptic curves, J. Reine Angew. Math. 447 (1994), 91–145.
  6. Andrew Childs, David Jao, and Vladimir Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, J. Math. Cryptol. 8 (2014), no. 1, 1–29.
  7. Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006.
  8. Marc Coppens and Gerriet Martens, Linear series on 4-gonal curves, Math. Nachr. 213 (2000), 35–55.
  9. Jean-Marc Couveignes, Hard homogeneous spaces, 2006. Cryptology e-Print Arxive.
  10. Luca De Feo, Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic, J. Number Theory 131 (2011), no. 5, 873–893.
  11. Luca De Feo, Cyril Hugounenq, Jérôme Plût, and Eric Schost,Éxplicit isogenies in quadratic time in any characteristic, LMS J. Comput. Math. 19 (2016), no. suppl. A, 267–282.
  12. Luca De Feo, David Jao, and Jérôme Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014), no. 3, 209–247.
  13. P. Deligne and D. Mumford, The irreducibility of the space of curves of given genus, Inst. Hautes Etudes Sci. Publ. Math.´ 36 (1969), 75–109.
  14. Max Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197–272.
  15. C. Diem, On arithmetic and the discrete logarithm problem in class groups of curves, Ph.D. Thesis, 2008. Habilitationsschrift.
  16. Claus Diem, An index calculus algorithm for plane curves of small degree, Algorithmic number theory, 2006, pp. 543–557.
  17. Whitfield Die and Martin E. Hellman, New directions in cryptography, IEEE Trans. Information Theory IT-22 (1976), no. 6, 644–654.
  18. J. Dixmier, On the projective invariants of quartic plane curves, Adv. in Math. 64 (1987), no. 3, 279–304.
  19. I. Dolgachev and D. Lehavi, On isogenous principally polarized abelian surfaces, Curves and abelian varieties, 2008, pp. 51–69.
  20. Ron Donagi and Ron Livné, The arithmetic-geometric mean and isogenies for curves of higher genus, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 28 (1999), no. 2, 323–339.
  21. Stéphane Flon, Roger Oyono, and Christophe Ritzenthaler, Fast addition on non-hyperelliptic genus 3 curves, Algebraic geometry and its applications, 2008, pp. 1–28.
  22. Gerhard Frey, Isogenies in theory and praxis, Open problems in mathematics and computational science, 2014, pp. 37–68.
  23. Gerhard Frey and Ernst Kani, Correspondences on hyperelliptic curves and applications to the discrete logarithm, 2011, pp. 1–19.
  24. ———, Normal forms of hyperelliptic curves of genus 3, Des. Codes Cryptogr. 77 (2015), no. 2-3, 677–712.
  25. William Fulton, Algebraic curves, Advanced Book Classics, Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1989. An introduction to algebraic geometry, Notes written with the collaboration of Richard Weiss, Reprint of 1969 original.
  26. P. Gaudry, F. Hess, and N. P. Smart, Constructive and destructive facets of Weil descent on elliptic curves, J. Cryptology 15 (2002), no. 1, 19–46.
  27. P. Gaudry, D. Kohel, B Smith, D. Hoon, and X. Wang, Counting points on genus 2 curves with real multiplication, 2011, pp. 504–519.
  28. P. Gaudry, E. Thomé, N. Thériault, and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, Math. Comp. 76 (2007), no. 257, 475–492.
  29. Pierrick Gaudry, David Kohel, and Benjamin Smith, Counting points on genus 2 curves with real multiplication, Advances in cryptology—ASIACRYPT 2011, 2011, pp. 504–519.
  30. F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445.
  31. Antoine Joux, Andrew Odlyzko, and Cécile Pierrot, The past, evolving present, and future of the discrete logarithm, Open problems in mathematics and computational science, 2014, pp. 5–36.
  32. Naoki Kanayama, Division polynomials and multiplication formulae of Jacobian varieties of dimension 2, Math. Proc. Cambridge Philos. Soc. 139 (2005), no. 3, 399–409.
  33. ———, Corrections to “Division polynomials and multiplication formulae in dimension 2”
  34. [mr2177167], Math. Proc. Cambridge Philos. Soc. 149 (2010), no. 1, 189–192.
  35. Kenji Koike and Annegret Weng, Construction of CM Picard curves, Math. Comp. 74 (2005), no. 249, 499–518.
  36. M. Kraichik, Théorie des nombres, paris, 1922.
  37. Greg Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Comput. 35 (2005), no. 1, 170–188.
  38. Frank Leitenberger, About the group law for the Jacobi variety of a hyperelliptic curve, Beiträge Algebra Geom. 46 (2005), no. 1, 125–130.
  39. Reynald Lercier and Christophe Ritzenthaler, Hyperelliptic curves and their invariants: geometric, arithmetic and algorithmic aspects, J. Algebra 372 (2012), 595–636.
  40. Davide Lombardo, Computing the geometric endomorphism ring of a genus 2 jacobian, arxiv (2016).
  41. David Lubicz and Damien Robert, Computing isogenies between abelian varieties, Compos. Math. 148 (2012), no. 5, 1483–1515.
  42. ———, Computing isogenies between abelian varieties, Compos. Math. 148 (2012), no. 5, 1483–1515.
  43. ———, Computing separable isogenies in quasi-optimal time, LMS J. Comput. Math. 18 (2015), no. 1, 198–216.
  44. K. Magaard, T. Shaska, S. Shpectorov, and H. Völklein, The locus of curves with prescribed automorphism group, S¯urikaisekikenky¯usho K¯oky¯uroku 1267 (2002), 112–141. Communications in arithmetic fundamental groups (Kyoto, 1999/2001).
  45. K. Magaard, T. Shaska, and H. Völklein, Genus 2 curves that admit a degree 5 map to an elliptic curve, Forum Math. 21 (2009), no. 3, 547–566.
  46. Andreas Malmendier and Tony Shaska, A universal genus-two curve from Siegel modular forms, SIGMA Symmetry Integrability Geom. Methods Appl. 13 (2017), 089, 17 pages.
  47. B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Etudes Sci. Publ. Math.´ 47 (1977), 33–186 (1978).
  48. J. S. Milne, Jacobian varieties, Arithmetic geometry (Storrs, Conn., 1984), 1986, pp. 167–212.
  49. David Mumford, Abelian varieties, Tata Institute of Fundamental Research Studies in Mathematics, vol. 5, Published for the Tata Institute of Fundamental Research, Bombay; by Hindustan Book Agency, New Delhi, 2008. With appendices by C. P. Ramanujam and Yuri Manin, Corrected reprint of the second (1974) edition.
  50. Yoshihiro Onishi,D̂eterminant expressions for hyperelliptic functions, Proc. Edinb. Math. Soc. (2) 48 (2005), no. 3, 705–742. With an appendix by Shigeki Matsutani.
  51. Frans Oort, Endomorphism algebras of abelian varieties, Algebraic geometry and commutative algebra, Vol. II, 1988, pp. 469–502.
  52. Oded Regev, New lattice-based cryptographic constructions, J. ACM 51 (2004), no. 6, 899–942.
  53. T. Shaska, Genus 2 fields with degree 3 elliptic subfields, Forum Math. 16 (2004), no. 2, 263–280.
  54. ———, Some remarks on the hyperelliptic moduli of genus 3, Comm. Algebra 42 (2014), no. 9, 4110–4130.
  55. ———, Heights on weighted projective spaces (201801), available at 1801.06250.
  56. T. Shaska and F. Thompson, Bielliptic curves of genus 3 in the hyperelliptic moduli, Appl. Algebra Engrg. Comm. Comput. 24 (2013), no. 5, 387–412.
  57. T. Shaska and J. L. Thompson, On the generic curve of genus 3, Ane algebraic geometry, 2005, pp. 233–243.
  58. T. Shaska and H. Völklein, Elliptic subfields and automorphisms of genus 2 function fields, Algebra, arithmetic and geometry with applications (West Lafayette, IN, 2000), 2004, pp. 703–723.
  59. Tetsuji Shioda, On the graded ring of invariants of binary octavics, Amer. J. Math. 89 (1967), 1022–1046.
  60. Benjamin Smith, Computing low-degree isogenies in genus 2 with the Dolgachev-Lehavi method, Arithmetic, geometry, cryptography and coding theory, 2012, pp. 159–170.
  61. Henning Stichtenoth, Algebraic function fields and codes, Second, Graduate Texts in Mathematics, vol. 254, Springer-Verlag, Berlin, 2009.
  62. 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.
  63. John Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math. 2 (1966), 134–144.
  64. Yukihiro Uchida, Division polynomials and canonical local heights on hyperelliptic Jacobians, Manuscripta Math. 134 (2011), no. 3-4, 273–308.
  65. Hermann-Josef Weber, Hyperelliptic simple factors of J0(N) with dimension at least 3, Experiment. Math. 6 (1997), no. 4, 273–287.
  66. Annegret Weng, A class of hyperelliptic CM-curves of genus three, J. Ramanujan Math. Soc. 16 (2001), no. 4, 339–372.

All preprints