Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Authors: M. D. Velichka, M. J. Jacobson Jr. and A. Stein
Journal: Math. Comp. 83 (2014), 935-963
MSC (2010): Primary 14G50; Secondary 11G20, 11Y16, 11Y40
DOI: https://doi.org/10.1090/S0025-5718-2013-02748-2
Published electronically: July 23, 2013
MathSciNet review: 3143699
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (96k:11152)
  • [2] ATLAS, Automatically tuned linear algebra software, Software, 2007, See http://math-atlas.sourceforge.net/.
  • [3] Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794 (97e:11157)
  • [4] D. Bernstein, How to find small factors of integers, to appear in Math. Comp.
  • [5] David G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), no. 177, 95-101. MR 866101 (88f:11118), https://doi.org/10.2307/2007876
  • [6] 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 (82e:12020), https://doi.org/10.2307/2007663
  • [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. MR 2162716 (2007f:14020)
  • [8] S. Contini, Factoring integers with the self-initializing quadratic sieve, Master's thesis, University of Georgia, Athens, Georgia, 1997.
  • [9] Richard Crandall and Carl Pomerance, Prime numbers, a computational perspective, Springer-Verlag, New York, 2001. MR 1821158 (2002a:11007)
  • [10] Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83-103. MR 1884958 (2002k:11225), https://doi.org/10.4064/aa102-1-6
  • [11] Ralf Flassenberg and Sachar Paulus, Sieving in function fields, Experiment. Math. 8 (1999), no. 4, 339-349. MR 1737230 (2000j:11179)
  • [12] 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
  • [13] Gerhard Frey, Applications of arithmetical geometry to cryptographic constructions, Finite fields and applications (Augsburg, 1999) Springer, Berlin, 2001, pp. 128-161. MR 1849086 (2002h:11136)
  • [14] 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, https://doi.org/10.1007/3-540-45539-6_2
  • [15] 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 (2003b:14032), https://doi.org/10.1007/s00145-001-0011-x
  • [16] 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 (electronic). MR 2261032 (2007j:11174), https://doi.org/10.1090/S0025-5718-06-01900-4
  • [17] 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, https://doi.org/10.1007/3-540-45539-6_2
  • [18] GCC, GCC, the GNU compiler collection, Software, 2007, see http://gcc.gnu.org/.
  • [19] GMP, The GNU multiple precision bignum library, Software, 2007, see http://gmplib.org/.
  • [20] J. F. Hammell, Index calculus in the infrastructure of real quadratic function fields, Master's thesis, University of Calgary, Canada, 2008.
  • [21] J. F. Hammell and M. J. Jacobson, Jr., Index-calculus algorithms in real quadratic function fields, In preparation, 2011.
  • [22] Michael J. Jacobson Jr., Applying sieving to the computation of quadratic class groups, Math. Comp. 68 (1999), no. 226, 859-867. MR 1604324 (99i:11120), https://doi.org/10.1090/S0025-5718-99-01003-0
  • [23] Michael J. Jacobson Jr., Subexponential class group computation in quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, Darmstadt, Germany, 1999.
  • [24] Michael J. Jacobson Jr., Computing discrete logarithms in quadratic orders, J. Cryptology 13 (2000), no. 4, 473-492. MR 1788516 (2003b:94046), https://doi.org/10.1007/s001450010013
  • [25] 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 (2002h:14039)
  • [26] 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 (2010a:14054), https://doi.org/10.1142/9789812772022_0013
  • [27] 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 (2000a:94012)
  • [28] Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203-209. MR 866109 (88b:94017), https://doi.org/10.2307/2007884
  • [29] Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139-150. MR 1007215 (90k:11165), https://doi.org/10.1007/BF02252872
  • [30] 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, https://doi.org/10.1007/BFb0091535
  • [31] LinBox, Project LinBox: Exact computational linear algebra, Software, 2007, see http://www.linalg.org/.
  • [32] 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 (2003k:94034), https://doi.org/10.1007/3-540-45311-3_19
  • [33] MPI, Message passing interface, Software, 2007, see http://www-unix.mcs.anl.gov/mpi/.
  • [34] 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 (88b:68040), https://doi.org/10.1007/3-540-39799-X_31
  • [35] 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 (99i:11119), https://doi.org/10.1090/S0025-5718-99-01040-6
  • [36] 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 (87d:11098), https://doi.org/10.1007/3-540-39757-4_17
  • [37] V. Shoup, NTL: A library for doing number theory, http://www.shoup.net, 2008.
  • [38] 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 (2000j:11199), https://doi.org/10.1007/BFb0054891
  • [39] 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 (2006d:94068), https://doi.org/10.1007/978-3-540-40061-5_5
  • [40] 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.
  • [41] 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 (2003b:11135), https://doi.org/10.1007/10722028_39
  • [42] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167 (2000j:68205)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14G50, 11G20, 11Y16, 11Y40

Retrieve articles in all journals with MSC (2010): 14G50, 11G20, 11Y16, 11Y40


Additional Information

M. D. Velichka
Affiliation: Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: markvelichka@gmail.com

M. J. Jacobson Jr.
Affiliation: Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: jacobs@cpsc.ucalgary.ca

A. Stein
Affiliation: Institut für Mathematik, Carl-von-Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany
Email: andreas.stein1@uni-oldenburg.de

DOI: https://doi.org/10.1090/S0025-5718-2013-02748-2
Keywords: Hyperelliptic curves, discrete logarithm problem, sieving, Weil descent
Received by editor(s): February 7, 2011
Received by editor(s) in revised form: July 3, 2012
Published electronically: July 23, 2013
Additional Notes: The first author’s research was supported by NSERC of Canada
The second author’s research was supported by NSERC of Canada
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society