×

Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields. (English) Zbl 1285.14031

The discrete logarithm problem in the Jacobian of elliptic and hyperelliptic curves has been extensively proposed as basis of many public-key cryptographic protocols. An interesting application of high genus hyperelliptic curves is that Weil descent can reduce the discrete logarithm problem on some elliptic curves over a finite field of composite degree to an instance of the same problem on an hyperelliptic curve of high genus defined over a smaller field. Under some assumptions this problem can be solve in subexponential time using index calculus algorithms.
The paper under review deals with the discrete logarithm problem in the Jacobian of high genus hyperelliptic curves defined over even characteristic finite fields and propose new improved versions of index-calculus algorithms. The first improvement is the incorporation of several ideas for the low-genus case given by P. Gaudry [Lect. Notes Comput. Sci. 1807, 19–34 (2000; Zbl 1082.94517)] and N. Thériault [Lect. Notes Comput. Sci. 2894, 75–92 (2003; Zbl 1205.94103)] and using a smaller factor basis into the algorithm of A. Enge and P. Gaudry [Acta Arith. 102, No. 1, 83–103 (2002; Zbl 1028.11079)]. The second improvement is the adaptation of of sieving techniques from R. Flassenberg and S. Paulus [Exp. Math. 8, No. 4, 339–349 (1999; Zbl 0942.11047)] and M. J. Jacobson jun. [Math. Comput. 68, No. 226, 859–867 (1999; Zbl 1036.11067)].
The resulting algorithms are applied to the same Weil descent examples as in [M. Jacobson et al., J. Ramanujan Math. Soc. 16, No. 3, 231–260 (2001; Zbl 1017.11030)], showing that the proposed versions lead to improved performance in practice.

MSC:

14G50 Applications to coding theory and cryptography of arithmetic geometry
11G20 Curves over finite and local fields
11Y16 Number-theoretic algorithms; complexity
11Y40 Algebraic number theory computations

Software:

gmp; NTL; ATLAS; LiDIA
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 0939.11038
[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. · Zbl 0873.11070
[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. · Zbl 0613.14022
[6] David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587 – 592. · Zbl 0493.12024
[7] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren , Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. · Zbl 1082.94001
[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, Springer-Verlag, New York, 2001. A computational perspective. · Zbl 1088.11001
[10] Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83 – 103. · Zbl 1028.11079 · doi:10.4064/aa102-1-6
[11] Ralf Flassenberg and Sachar Paulus, Sieving in function fields, Experiment. Math. 8 (1999), no. 4, 339 – 349. · Zbl 0942.11047
[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. · Zbl 1015.94545
[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. · Zbl 1082.94517 · doi: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. · Zbl 0996.94036 · doi: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. · Zbl 1179.94062
[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. · Zbl 1082.94517 · doi: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. · Zbl 1036.11067
[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. · Zbl 0979.11059 · doi: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. · Zbl 1017.11030
[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. · Zbl 1132.14306 · doi: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. · Zbl 0890.94001
[28] Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203 – 209. · Zbl 0622.94015
[29] Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139 – 150. · Zbl 0674.94010 · doi: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. · Zbl 0806.11063 · doi: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. · Zbl 1055.94020 · doi: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. · doi: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. · Zbl 1036.11064
[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. · doi: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. · Zbl 1066.11513 · doi: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. · Zbl 1205.94103 · doi: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. · Zbl 1032.11064 · doi:10.1007/10722028_39
[42] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. · Zbl 0936.11069
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.