Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields

Velichka, M.; Jacobson, M., Jr.; Stein, A.

doi:10.1090/S0025-5718-2013-02748-2

Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
HTML articles powered by AMS MathViewer

by M. D. Velichka, M. J. Jacobson Jr. and A. Stein PDF

Math. Comp. 83 (2014), 935-963 Request permission

Abstract:

We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Thériault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in a 2001 paper by Jacobson, Menzes, and Stein to our new algorithm, allowing us to predict accurately the number of random walk steps required to find all relations, and to select optimal degree bounds for the factor base. Our second improvement is the adaptation of sieving techniques from Flassenberg and Paulus, and Jacobson to our setting. The new algorithms are applied to concrete problem instances arising from the Weil descent attack methodology for solving the elliptic curve discrete logarithm problem, demonstrating significant improvements in practice.

References

W. R. Alford and Carl Pomerance, Implementing the self-initializing quadratic sieve on a distributed network, Number-theoretic and algebraic methods in computer science (Moscow, 1993) World Sci. Publ., River Edge, NJ, 1995, pp. 163–174. MR 1377748
ATLAS, Automatically tuned linear algebra software, Software , 2007, See http://math-atlas.sourceforge.net/.
Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
D. Bernstein, How to find small factors of integers, to appear in Math. Comp.
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
David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
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. MR 2162716
S. Contini, Factoring integers with the self-initializing quadratic sieve, Master’s thesis, University of Georgia, Athens, Georgia, 1997.
Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83–103. MR 1884958, DOI 10.4064/aa102-1-6
Ralf Flassenberg and Sachar Paulus, Sieving in function fields, Experiment. Math. 8 (1999), no. 4, 339–349. MR 1737230
G. Frey, How to disguise an elliptic curve (Weil descent), Talk at ECC ’98, Waterloo, 1998. Slides available from http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/slides.html
Gerhard Frey, Applications of arithmetical geometry to cryptographic constructions, Finite fields and applications (Augsburg, 1999) Springer, Berlin, 2001, pp. 128–161. MR 1849086
Pierrick Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, Advances in cryptology—EUROCRYPT 2000 (Bruges), Lecture Notes in Comput. Sci., vol. 1807, Springer, Berlin, 2000, pp. 19–34. MR 1772021, DOI 10.1007/3-540-45539-6_{2}
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. MR 1880933, DOI 10.1007/s00145-001-0011-x
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. MR 2261032, DOI 10.1090/S0025-5718-06-01900-4
Pierrick Gaudry, An algorithm for solving the discrete log problem on hyperelliptic curves, Advances in cryptology—EUROCRYPT 2000 (Bruges), Lecture Notes in Comput. Sci., vol. 1807, Springer, Berlin, 2000, pp. 19–34. MR 1772021, DOI 10.1007/3-540-45539-6_{2}
GCC, GCC, the GNU compiler collection, Software , 2007, see http://gcc.gnu.org/.
GMP, The GNU multiple precision bignum library, Software , 2007, see http://gmplib.org/.
J. F. Hammell, Index calculus in the infrastructure of real quadratic function fields, Master’s thesis, University of Calgary, Canada, 2008.
J. F. Hammell and M. J. Jacobson, Jr., Index-calculus algorithms in real quadratic function fields, In preparation, 2011.
Michael J. Jacobson Jr., Applying sieving to the computation of quadratic class groups, Math. Comp. 68 (1999), no. 226, 859–867. MR 1604324, DOI 10.1090/S0025-5718-99-01003-0
Michael J. Jacobson Jr., Subexponential class group computation in quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, Darmstadt, Germany, 1999.
Michael J. Jacobson Jr., Computing discrete logarithms in quadratic orders, J. Cryptology 13 (2000), no. 4, 473–492. MR 1788516, DOI 10.1007/s001450010013
Michael Jacobson, Alfred Menezes, and Andreas Stein, Solving elliptic curve discrete logarithm problems using Weil descent, J. Ramanujan Math. Soc. 16 (2001), no. 3, 231–260. MR 1863606
M. J. Jacobson Jr., R. Scheidler, and A. Stein, Fast arithmetic on hyperelliptic curves via continued fraction expansions, Advances in coding theory and cryptography, Ser. Coding Theory Cryptol., vol. 3, World Sci. Publ., Hackensack, NJ, 2007, pp. 200–243. MR 2454114, DOI 10.1142/9789812772022_{0}013
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
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
H. W. Lenstra Jr., The number field sieve: an annotated bibliography, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 1–3. MR 1321217, DOI 10.1007/BFb0091535
LinBox, Project LinBox: Exact computational linear algebra, Software , 2007, see http://www.linalg.org/.
Markus Maurer, Alfred Menezes, and Edlyn Teske, Analysis of the GHS Weil descent attack on the ECDLP over characteristic two finite fields of composite degree, LMS J. Comput. Math. 5 (2002), 127–174. MR 1942257, DOI 10.1007/3-540-45311-3_{1}9
MPI, Message passing interface, Software , 2007, see http://www-unix.mcs.anl.gov/mpi/.
Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417–426. MR 851432, DOI 10.1007/3-540-39799-X_{3}1
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
Carl Pomerance, The quadratic sieve factoring algorithm, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 169–182. MR 825590, DOI 10.1007/3-540-39757-4_{1}7
V. Shoup, NTL: A library for doing number theory, http://www.shoup.net, 2008.
Edlyn Teske, Speeding up Pollard’s rho method for computing discrete logarithms, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 541–554. MR 1726100, DOI 10.1007/BFb0054891
Nicolas Thériault, Index calculus attack for hyperelliptic curves of small genus, Advances in cryptology—ASIACRYPT 2003, Lecture Notes in Comput. Sci., vol. 2894, Springer, Berlin, 2003, pp. 75–92. MR 2093253, DOI 10.1007/978-3-540-40061-5_{5}
M. D. Velichka, Improvements to index calculus algorithms for solving the hyperelliptic curve discrete logarithm problem over characteristic two finite fields, Master’s thesis, University of Calgary, Canada, 2008.
Ulrich Vollmer, Asymptotically fast discrete logarithms in quadratic number fields, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 581–594. MR 1850635, DOI 10.1007/10722028_{3}9
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167