×

Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with \((\ell ,\ell ,\ell)\)-isogenies. (English) Zbl 1467.14107

Summary: We give an algorithm to compute \((\ell,\ell,\ell)\)-isogenies from the Jacobians of genus three hyperelliptic curves to the Jacobians of non-hyperelliptic curves over a finite field of characteristic different from 2 in time \(\tilde{O}(\ell^3)\), where \(\ell\) is an odd prime which is coprime to the characteristic. An important application is to reduce the discrete logarithm problem in the Jacobian of a hyperelliptic curve to the corresponding problem in the Jacobian of a non-hyperelliptic curve.

MSC:

14K02 Isogeny
14H40 Jacobians, Prym varieties
14K25 Theta functions and abelian varieties
94A60 Cryptography
14K10 Algebraic moduli of abelian varieties, classification
14G50 Applications to coding theory and cryptography of arithmetic geometry
14H05 Algebraic functions and function fields in algebraic geometry
94A62 Authentication, digital signatures and secret sharing
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Beauville, A., The Coble hypersurfaces, C. R. Math., 337, 3, 189-194 (2003) · Zbl 1075.14042 · doi:10.1016/S1631-073X(03)00302-9
[2] A. Beauville, Vector bundles on curves and theta functions. Adv. Stud. Pure Math., pp. 145-156, (2005) · Zbl 1115.14025
[3] Beauville, A.; Ritzenthaler, C., Jacobians among abelian threefolds: a geometric approach, Math. Ann., 350, 4, 793-799 (2011) · Zbl 1228.14027 · doi:10.1007/s00208-010-0583-6
[4] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125
[5] Cosset, R.; Robert, D., Computing \((\ell ,\ell )\)-isogenies in polynomial time on Jacobians of genus 2 curves, Math. Comput., 84, 294, 1953-1975 (2015) · Zbl 1315.11103 · doi:10.1090/S0025-5718-2014-02899-8
[6] Couveignes, J., Linearizing torsion classes in the Picard group of algebraic curves over finite fields, J. Algeb., 321, 8, 2085-2118 (2009) · Zbl 1168.14007 · doi:10.1016/j.jalgebra.2008.09.032
[7] Couveignes, J.; Ezome, T., Computing functions on Jacobians and their quotients, LMS J. Comput. Math., 18, 1, 555-577 (2015) · Zbl 1333.14038 · doi:10.1112/S1461157015000169
[8] Diem, C.; Thomé, E., Index calculus in class groups of non-hyperelliptic curves of genus three, J. Cryptol., 21, 4, 593-611 (2008) · Zbl 1167.11047 · doi:10.1007/s00145-007-9014-6
[9] Dolgachev, IV; Lehavi, D., On isogenous principally polarized abelian surfaces, AMS Contemp. Math., 465, 51-69 (2008) · Zbl 1152.14306 · doi:10.1090/conm/465/09100
[10] Donagi, R.; Livné, R., The arithmetic-geometric mean and isogenies for curves of higher genus, Annali Della Scuola Normale Superiore Di Pisa-classe Di Scienze, 28, 2, 323-339 (1999) · Zbl 0962.14021
[11] A. Fiorentino, Weber’s formula for the bitangents of a smooth plane quartic. Algebraic Geometry (2016). arXiv:1612.02049 · Zbl 1451.14102
[12] E.V. Flynn, Y.B. Ti, Genus two isogeny cryptography, in J. Ding, R. Steinwandt, editors, Post-Quantum Cryptography, (Springer, Cham, 2019), pp. 286-306 · Zbl 1510.94082
[13] G. Frey, E. Kani, Correspondences on hyperelliptic curves and applications to the discrete logarithm. In P. Bouvry, M.A. Kłopotek, F. Leprévost, M. Marciniak, A. Mykowiecka, H. Rybiński, editors, Security and Intelligent Information Systems (Springer, Berlin, 2011), pp. 1-19 · Zbl 1345.14036
[14] Gaudry, P.; Thomé, E.; Thériault, N.; Diem, C., A double large prime variation for small genus hyperelliptic index calculus, Math. Comput., 76, 257, 475-492 (2007) · Zbl 1179.94062 · doi:10.1090/S0025-5718-06-01900-4
[15] D. Jao, L. De Feo, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In B.-Y. Yang, editor, Post-Quantum Cryptography, (Springer, Berlin, 2011), pp. 19-34 · Zbl 1290.94094
[16] Koizumi, S., Theta relations and projective normality of abelian varieties, Am. J. Math., 98, 4, 865-889 (1976) · Zbl 0347.14023 · doi:10.2307/2374034
[17] Lercier, R.; Ritzenthaler, C.; Sijsling, J., Reconstructing plane quartics from their invariants, Discret. Comput. Geom., 63, 1, 73-113 (2020) · Zbl 1439.13020 · doi:10.1007/s00454-018-0047-4
[18] Lubicz, D.; Robert, D., Computing isogenies between abelian varieties, Compos. Math., 148, 5, 1483-1515 (2012) · Zbl 1259.14047 · doi:10.1112/S0010437X12000243
[19] Milio, E., Computing isogenies between Jacobians of curves of genus 2 and 3, Math. Comput., 89, 1331-1364 (2020) · Zbl 1433.14043 · doi:10.1090/mcom/3486
[20] Mumford, D., On the equations defining abelian varieties, I. Invent. Math., 1, 4, 287-354 (1966) · Zbl 0219.14024 · doi:10.1007/BF01389737
[21] Mumford, D., Abelian Varieties (1974), Oxford: Oxford University Press, Oxford · Zbl 0326.14012
[22] D. Mumford, Tata Lectures on Theta I. Birkhäuser, (1984)
[23] D. Mumford, Tata Lectures on Theta II. Birkhäuser, (1984) · Zbl 0549.14014
[24] F. Oort, K. Ueno, Principally polarized abelian variaties dimension two or three are Jacobian varieties. J. Faculty Sci. Univ. Tokyo Sect. IA. Math., (20), 377-381, (1973) · Zbl 0272.14008
[25] Recillas, S., Jacobians of curves with \(g_1^4\)’s are the Pryms of trigonal curves, Boletín de la Sociedad Matemática Mexicana, 19, 1, 9-13 (1974) · Zbl 0343.14012
[26] Ren, Q.; Sam, SV; Schrader, G.; Sturmfels, B., The universal Kummer threefold, Exp. Math., 22, 3, 327-362 (2013) · Zbl 1312.14103 · doi:10.1080/10586458.2013.816206
[27] C. Ritzenthaler, Point counting on genus 3 non-hyperelliptic curves. Algor. Number Theory Symp., pp. 379-394, (2004) · Zbl 1125.11331
[28] N. Shepherd-Barron, Thomae’s formulae for non-hyperelliptic curves and spinorial square roots of theta-constants on the moduli space of curves. Algebraic Geometry (2008). arXiv:0802.3014
[29] Smith, B., Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves, J. Cryptol., 22, 4, 505-529 (2009) · Zbl 1182.94047 · doi:10.1007/s00145-009-9038-1
[30] Smith, B., Computing low-degree isogenies in genus 2 with the Dolgachev-Lehavi method, AMS Contemp. Math., 574, 159-170 (2012) · Zbl 1317.11133 · doi:10.1090/conm/574/11418
[31] Vélu, J., Isogénies entre courbes elliptiques, Compte Rendu Académie Sciences Paris Série, 273, A238-A241 (1971) · Zbl 0225.14014
[32] H. Weber, Theorie der Abelschen Functionen vom Geschlecht drei. (Cornell University Library, New York, 1876) · JFM 08.0293.01
[33] H. Weber, Bernhard Riemann’s Gesammelte Mathematische Werke und Wissenschaftlicher Nachlass, pp. 487-504. Druck und verlag von B.G. Teubner, Leipzig, (1892) · JFM 24.0021.04
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.