A double large prime variation for small genus hyperelliptic index calculus

Gaudry, P.; Thomé, E.; Thériault, N.; Diem, C.

doi:10.1090/S0025-5718-06-01900-4

A double large prime variation for small genus hyperelliptic index calculus
HTML articles powered by AMS MathViewer

by P. Gaudry, E. Thomé, N. Thériault and C. Diem PDF

Math. Comp. 76 (2007), 475-492 Request permission

Abstract:

In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard’s Rho method even for rather small field sizes.

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
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
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
Fan Chung and Linyuan Lu, The diameter of sparse random graphs, Adv. in Appl. Math. 26 (2001), no. 4, 257–279. MR 1826308, DOI 10.1006/aama.2001.0720
Don Coppersmith, Solving homogeneous linear equations over $\textrm {GF}(2)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), no. 205, 333–350. MR 1192970, DOI 10.1090/S0025-5718-1994-1192970-7
Jean-Marc Couveignes, Algebraic groups and discrete logarithm, Public-key cryptography and computational number theory (Warsaw, 2000) de Gruyter, Berlin, 2001, pp. 17–27. MR 1881624
C. Diem, Index calculus algorithm for plane curves of small degree, ANTS-VII (F. Heß, S. Pauli and M. Pohst, eds.), Lecture Notes in Comput. Sci., vol. 4076, Springer-Verlag, 2006, pp. 543–557.
Andreas Enge, Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time, Math. Comp. 71 (2002), no. 238, 729–742. MR 1885624, DOI 10.1090/S0025-5718-01-01363-1
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
Philippe Flajolet, Donald E. Knuth, and Boris Pittel, The first cycles in an evolving graph, Discrete Math. 75 (1989), no. 1-3, 167–215. Graph theory and combinatorics (Cambridge, 1988). MR 1001395, DOI 10.1016/0012-365X(89)90087-3
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}
—, Index calculus for abelian varieties and the elliptic curve discrete logarithm problem, Cryptology ePrint Archive: Report 2004/073, 2004.
F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
—, Computing relations in divisor class groups of algebraic curves over finite fields, Preprint, 2004.
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
A. K. Lenstra and M. S. Manasse, Factoring with two large primes, Math. Comp. 63 (1994), no. 208, 785–798. MR 1250773, DOI 10.1090/S0025-5718-1994-1250773-9
Paul Leyland, Arjen Lenstra, Bruce Dodson, Alec Muffett, and Sam Wagstaff, MPQS with three large primes, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 446–460. MR 2041103, DOI 10.1007/3-540-45455-1_{3}5
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
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
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
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}
Emmanuel Thomé, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, J. Symbolic Comput. 33 (2002), no. 5, 757–775. Computer algebra (London, ON, 2001). MR 1919913, DOI 10.1006/jsco.2002.0533
—, Algorithmes de calcul de logarithme discret dans les corps finis, Thèse, École polytechnique, May, 2003.
Emil J. Volcheck, Computing in the Jacobian of a plane algebraic curve, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 221–233. MR 1322725, DOI 10.1007/3-540-58691-1_{6}0
T. Wollinger, J. Pelzl, and C. Paar, Cantor versus Harley: Optimization and analysis of explicit formulae for hyperelliptic curve cryptosystem, Tech. report, Universität Bochum, 2004, Available at http://www.crypto.rub.de/.