Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time

Enge, Andreas

doi:10.1090/S0025-5718-01-01363-1

Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time
HTML articles powered by AMS MathViewer

by Andreas Enge PDF

Math. Comp. 71 (2002), 729-742 Request permission

Abstract:

We provide a subexponential algorithm for solving the discrete logarithm problem in Jacobians of high-genus hyperelliptic curves over finite fields. Its expected running time for instances with genus $g$ and underlying finite field $\mathbb {F}_q$ satisfying $g \geq \vartheta \log q$ for a positive constant $\vartheta$ is given by \[ O \left ( e^{ \left ( \frac {5}{\sqrt 6} \left ( \sqrt {1 + \frac {3}{2 \vartheta }} + \sqrt {\frac {3}{2 \vartheta }} \right ) + o (1) \right ) \sqrt {(g \log q) \log (g \log q)}} \right ). \] The algorithm works over any finite field, and its running time does not rely on any unproven assumptions.

References

Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 28–40. MR 1322708, DOI 10.1007/3-540-58691-1_{3}9
Leonard M. Adleman and Ming-Deh Huang (eds.), Algorithmic number theory, Lecture Notes in Computer Science, vol. 877, Springer-Verlag, Berlin, 1994. MR 1322704, DOI 10.1007/3-540-58691-1
E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen II, Math. Z. 19 (1924), 207–246.
Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698
David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95–101. MR 866101, DOI 10.1090/S0025-5718-1987-0866101-0
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Henri Cohen (ed.), Algorithmic number theory, Lecture Notes in Computer Science, vol. 1122, Springer-Verlag, Berlin, 1996. MR 1446492, DOI 10.1007/3-540-61581-4
P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50–59. MR 882842, DOI 10.1287/moor.12.1.50
Stephan Düllmann, Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter binärer quadratischer Formen, Dissertation, Universität des Saarlandes, Saarbrücken, 1991.
Andreas Enge, The extended Euclidian algorithm on polynomials, and the computational efficiency of hyperelliptic cryptosystems, Des. Codes Cryptogr., 23 (2001), 53–74.
—, Hyperelliptic cryptosystems: Efficiency and subexponential attacks, Dissertation, Universität Augsburg, 2000, ISBN 3-8311-1868-X.
—, How to distinguish hyperelliptic curves in even characteristic, to appear in Proceedings of the Conference on Public Key Cryptography and Computational Number Theory, Warszawa 2000.
Andreas Enge and Andreas Stein, Smooth ideals in hyperelliptic function fields, Math. Comp., posted on October 4, 2001, PII S0025-5718(01)01352-7 (to appear in print).
Ralf Flassenberg and Sachar Paulus, Sieving in function fields, Experiment. Math. 8 (1999), no. 4, 339–349. MR 1737230
Catherine Goldstein (ed.), Séminaire de Théorie des Nombres, Paris 1988–1989, Progress in Mathematics, vol. 91, Birkhäuser Boston, Inc., Boston, MA, 1990. Papers from the seminar held in Paris, 1988–1989. MR 1104695, DOI 10.1007/978-1-4612-3460-9
Ming-Deh Huang and Doug Ierardi, Counting points on curves over finite fields, J. Symbolic Comput. 25 (1998), no. 1, 1–21. MR 1600606, DOI 10.1006/jsco.1997.0164
Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
Neal Koblitz, Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, vol. 3, Springer-Verlag, Berlin, 1998. With an appendix by Alfred J. Menezes, Yi-Hong Wu and Robert J. Zuccherato. MR 1610535, DOI 10.1007/978-3-662-03642-6
A. K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 443–454. MR 976527
Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459–479. MR 1123090
Neal Koblitz, Algebraic aspects of cryptography, Algorithms and Computation in Mathematics, vol. 3, Springer-Verlag, Berlin, 1998. With an appendix by Alfred J. Menezes, Yi-Hong Wu and Robert J. Zuccherato. MR 1610535, DOI 10.1007/978-3-662-03642-6
Richard A. Mollin (ed.), Number theory and applications, NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, vol. 265, Kluwer Academic Publishers Group, Dordrecht, 1989. MR 1123065
Achim Müller, Effiziente Algorithmen für Probleme der linearen Algebra über $\mathbb {Z}$, Diplomarbeit, Universität des Saarlandes, Saarbrücken, 1994.
Volker Müller, Andreas Stein, and Christoph Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), no. 226, 807–822. MR 1620235, DOI 10.1090/S0025-5718-99-01040-6
J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763. MR 1035941, DOI 10.1090/S0025-5718-1990-1035941-X
Bjorn Poonen, Computational aspects of curves of genus at least $2$, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 283–306. MR 1446520, DOI 10.1007/3-540-61581-4_{6}3
Andreas Stein, Algorithmen in reell-quadratischen Kongruenzfunktionenkörpern, Dissertation, Universität des Saarlandes, Saarbrücken, 1996.