×

Cycles in the supersingular \(\ell \)-isogeny graph and corresponding endomorphisms. (English) Zbl 1436.11148

Balakrishnan, Jennifer S. (ed.) et al., Research directions in number theory. Women in numbers IV. Proceedings of the women in numbers, WIN4 workshop. Banff International Research Station, Banff, Alberta, Canada, August 14–18, 2017. Cham: Springer. Assoc. Women Math. Ser. 19, 41-66 (2019).
Summary: We study the problem of generating the endomorphism ring of a supersingular elliptic curve by two cycles in \(\ell \)-isogeny graphs. We prove a necessary and sufficient condition for the two endomorphisms corresponding to two cycles to be linearly independent, expanding on the work by D. Kohel in his thesis [Endomorphism rings of elliptic curves over finite fields. Berkeley, CA: University of California (PhD Thesis) (1996)]. We also give a criterion under which the ring generated by two cycles is not a maximal order. We give some examples in which we compute cycles which generate the full endomorphism ring. The most difficult part of these computations is the calculation of the trace of these cycles. We show that a generalization of Schoof’s algorithm can accomplish this computation efficiently.
For the entire collection see [Zbl 1428.11002].

MSC:

11Y16 Number-theoretic algorithms; complexity
11G20 Curves over finite and local fields
94A60 Cryptography
14Q05 Computational aspects of algebraic curves
11G05 Elliptic curves over global fields
11R52 Quaternion and other division algebras: arithmetic, zeta functions
14H52 Elliptic curves
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, David Jao, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Joost Renes, Vladimir Soukharev, and David Urbanik. Supersingular isogeny key encapsulation. Submission to the NIST Post-Quantum Standardization project, 2017. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions.
[2] Jean-François Biasse, David Jao, and Anirudh Sankar. A quantum algorithm for computing isogenies between supersingular elliptic curves. In Progress in cryptology—INDOCRYPT 2014, volume 8885 of Lecture Notes in Comput. Sci., pages 428-442. Springer, Cham, 2014. · Zbl 1337.94024
[3] A. Bostan, F. Morain, B. Salvy, and É. Schost. Fast algorithms for computing isogenies between elliptic curves. Math. Comp., 77(263):1755-1778, 2008. · Zbl 1200.11097 · doi:10.1090/S0025-5718-08-02066-8
[4] J. M. Cerviño. Supersingular elliptic curves and maximal quaternionic orders. In Mathematisches Institut, Georg-August-Universität Göttingen: Seminars Summer Term 2004, pages 53-60. Universitätsdrucke Göttingen, Göttingen, 2004. · Zbl 1097.11028
[5] Ilya Chevyrev and Steven D. Galbraith. Constructing supersingular elliptic curves with a given endomorphism ring. LMS J. Comput. Math., 17(suppl. A):71-91, 2014. · Zbl 1326.11029 · doi:10.1112/S1461157014000254
[6] Denis X. Charles, Eyal Z. Goren, and Kristin Lauter. Cryptographic hash functions from expander graphs. J. Cryptology, 22(1):93-113, 2009. · Zbl 1166.94006 · doi:10.1007/s00145-007-9002-x
[7] Max Deuring. Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abh. Math. Sem. Hansischen Univ., 14:197-272, 1941. · Zbl 0025.02003 · doi:10.1007/BF02940746
[8] Luca De Feo, David Jao, and Jérôme Plût. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol., 8(3):209-247, 2014. · Zbl 1372.94419
[9] Christina Delfs and Steven D. Galbraith. Computing isogenies between supersingular elliptic curves over \(\mathbb{F}_p\). Des. Codes Cryptogr., 78(2):425-440, 2016. · Zbl 1361.11044
[10] Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, and Christophe Petit. Supersingular isogeny graphs and endomorphism rings: reductions and solutions. Eurocrypt 2018, LNCS 10822, pages 329-368, 2018. · Zbl 1415.94426
[11] Steven D. Galbraith, Christophe Petit, and Javier Silva. Identification protocols and signature schemes based on supersingular isogeny problems. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017, pages 3-33, Cham, 2017. Springer International Publishing. · Zbl 1420.94065
[12] David Kohel, Kristin Lauter, Christophe Petit, and Jean-Pierre Tignol. On the quaternion l-isogeny path problem. LMS Journal of Computation and Mathematics, 17:418-432, 2014. · Zbl 1296.11153 · doi:10.1112/S1461157014000151
[13] David Kohel. Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California, Berkeley, 1996.
[14] Kristin Lauter and Ken McMurdy. Explicit generators of endomorphism rings of supersingular elliptic curves. Preprint, 2004.
[15] Ken McMurdy. Explicit representation of the endomorphism rings of supersingular elliptic curves. https://phobos.ramapo.edu/ kmcmurdy/research/McMurdy-ssEndoRings.pdf, 2014.
[16] J.-F. Mestre. La méthode des graphes. Exemples et applications. In Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986), pages 217-242. Nagoya Univ., Nagoya, 1986. · Zbl 0621.14021
[17] Gabriele Nebe. Finite quaternionic matrix groups. Represent. Theory, 2:106-223, 1998. · Zbl 0901.20035 · doi:10.1090/S1088-4165-98-00011-9
[18] NIST. Post-quantum cryptography, 2016. csrc.nist.gov/Projects/Post-Quantum-Cryptography; accessed 30-September-2017.
[19] Arnold Pizer. An algorithm for computing modular forms on Γ_0(N). J. Algebra, 64(2):340-390, 1980. · Zbl 0433.10012 · doi:10.1016/0021-8693(80)90151-9
[20] René Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44(170):483-494, 1985. · Zbl 0579.14025
[21] René Schoof. Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux, 7(1):219-254, 1995. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). · Zbl 0852.11073
[22] J.H. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics. Springer New York, 2009. · Zbl 1194.11005 · doi:10.1007/978-0-387-09494-6
[23] Igor E. Shparlinski and Andrew V. Sutherland. On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average. LMS J. Comput. Math., 18(1):308-322, 2015. · Zbl 1400.11164 · doi:10.1112/S1461157015000017
[24] Andrew V. Sutherland. Isogeny volcanoes. In ANTS X—Proceedings of the Tenth Algorithmic Number Theory Symposium, volume 1 of Open Book Ser., pages 507-530. Math. Sci. Publ., Berkeley, CA, 2013. · Zbl 1345.11044
[25] Jacques Vélu. Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. A-B, 273:A238-A241, 1971. · Zbl 0225.14014
[26] John Voight. Quaternion Algebras. v.0.9.12, March 29, 2018.
[27] William C. Waterhouse. Abelian varieties over finite fields. Ann. Sci. École Norm. Sup. (4), 2:521-560, 1969. · Zbl 0188.53001 · doi:10.24033/asens.1183
[28] Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao, and Vladimir Soukharev.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.