A generic approach to searching for Jacobians

Sutherland, Andrew

doi:10.1090/S0025-5718-08-02143-1

A generic approach to searching for Jacobians
HTML articles powered by AMS MathViewer

by Andrew V. Sutherland PDF

Math. Comp. 78 (2009), 485-507

Abstract:

We consider the problem of finding cryptographically suitable Jacobians. By applying a probabilistic generic algorithm to compute the zeta functions of low genus curves drawn from an arbitrary family, we can search for Jacobians containing a large subgroup of prime order. For a suitable distribution of curves, the complexity is subexponential in genus 2, and $O(N^{1/12})$ in genus 3. We give examples of genus 2 and genus 3 hyperelliptic curves over prime fields with group orders over $180$ bits in size, improving previous results. Our approach is particularly effective over low-degree extension fields, where in genus 2 we find Jacobians over $\mathbb {F}_{p^2}$ and trace zero varieties over $\mathbb {F}_{p^3}$ with near-prime orders up to 372 bits in size. For $p = 2^{61}-1$, the average time to find a group with 244-bit near-prime order is under an hour on a PC.

References

Eric Bach and René Peralta, Asymptotic semismoothness probabilities, Math. Comp. 65 (1996), no. 216, 1701–1715. MR 1370848, DOI 10.1090/S0025-5718-96-00775-2
Abdolali Basiri, Andreas Enge, Jean-Charles Faugère, and Nicolas Gürel, Implementing the arithmetic of $C_{3,4}$ curves, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 87–101. MR 2137346, DOI 10.1007/978-3-540-24847-7_{6}
Abdolali Basiri, Andreas Enge, Jean-Charles Faugère, and Nicolas Gürel, The arithmetic of Jacobian groups of superelliptic cubics, Math. Comp. 74 (2005), no. 249, 389–410. MR 2085899, DOI 10.1090/S0025-5718-04-01699-0
Daniel J. Bernstein, Elliptic vs. hyperelliptic, part 1, 2006, Talk given at ECC 2006, http://cr.yp.to/talks/2006.09.20/slides.pdf.
Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777–1806. MR 2299425, DOI 10.1137/S0097539704443793
Johannes Buchmann, Michael J. Jacobson Jr., and Edlyn Teske, On some computational problems in finite abelian groups, Math. Comp. 66 (1997), no. 220, 1663–1687. MR 1432126, DOI 10.1090/S0025-5718-97-00880-6
Johannes Buchmann and Arthur Schmidt, Computing the structure of a finite abelian group, Math. Comp. 74 (2005), no. 252, 2017–2026. MR 2164109, DOI 10.1090/S0025-5718-05-01740-0
E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
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, 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
Certicom Corporation, Certicom ECC challenge, 1997, see http://www.certicom.com.
K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Arkiv för Mathematik, Astronomi, och Fysik, 22A 10 (1930), 1–14.
Claus Diem, The GHS attack in odd characteristic, J. Ramanujan Math. Soc. 18 (2003), no. 1, 1–32. MR 1966526
Claus Diem, An index calculus algorithm for plane curves of small degree, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 4076, Springer, Berlin, 2006, pp. 543–557. MR 2282948, DOI 10.1007/11792086_{3}8
Claus Diem and Jasper Scholten, Cover attacks: A report for the AREHCC project, 2003, http://www.math.uni-leipzig.de/~diem/preprints/cover-attacks.pdf.
Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21–76. MR 1486831, DOI 10.1090/amsip/007/03
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
Stéphane Flon and Roger Oyono, Fast arithmetic on Jacobians of Picard curves, Public Key Cryptography–PKC 2004, Lecture Notes in Computer Science, vol. 2947, 2004, pp. 55–68.
Stéphane Flon, Roger Oyono, and Christophe Ritzenhaler, Fast addition on non-hyperelliptic genus $3$ curves, Tech. Report CACR 2007-19, Center for Applied Cryptographic Research at the University of Waterloo, 2007.
Gerhard Frey, Applications of arithmetical geometry to cryptographic constructions, Finite fields and applications (Augsburg, 1999) Springer, Berlin, 2001, pp. 128–161. MR 1849086
Eisaku Furukawa, Mitsuru Kawazoe, and Tetsuya Takahashi, Counting points for hyperelliptic curves of type $y^2=x^5+ax$ over finite prime fields, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3006, Springer, Berlin, 2004, pp. 26–41. MR 2094719, DOI 10.1007/978-3-540-24654-1_{3}
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, Index calculus for abelian varieties and the elliptic curve discrete logarithm problem, Cryptology ePrint Archive, Report 2004/073, 2004, http://eprint.iacr.org/.
—, Fast genus $2$ arithmetic based on Theta functions, 2005, to appear in Journal of Mathematical Cryptology, http://www.loria.fr/~gaudry/publis/arithKsurf.ps.gz.
Pierrick Gaudry and Éric Schost, Construction of secure random curves of genus 2 over prime fields, Advances in cryptology—EUROCRYPT 2004, Lecture Notes in Comput. Sci., vol. 3027, Springer, Berlin, 2004, pp. 239–256. MR 2153176, DOI 10.1007/978-3-540-24676-3_{1}5
Pierrick Gaudry and Nicolas Gürel, Counting points in medium characteristic using Kedlaya’s algorithm, Experiment. Math. 12 (2003), no. 4, 395–402. MR 2043990
Torbjörn Granlund et al., GNU multiple precision arithmetic library 4.2.1, May 2006, http://swox.com/gmp/.
David Harvey, Kedlaya’s algorithm in larger characteristic, International Mathematical Research Notices (2007).
Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338. MR 1877805
Kiran S. Kedlaya, Computing zeta functions via $p$-adic cohomology, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 1–17. MR 2137340, DOI 10.1007/978-3-540-24847-7_{1}
Kamal Khuri-Makdisi, Asymptotically fast group operations on Jacobians of general curves, Math. Comp. 76 (2007), no. 260, 2213–2239. MR 2336292, DOI 10.1090/S0025-5718-07-01989-8
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
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
Tanja Lange, Trace zero subvarieties of genus 2 curves for cryptosystems, J. Ramanujan Math. Soc. 19 (2004), no. 1, 15–33. MR 2054607
Tanja Lange, Formulae for arithmetic on genus 2 hyperelliptic curves, Appl. Algebra Engrg. Comm. Comput. 15 (2005), no. 5, 295–328. MR 2122308, DOI 10.1007/s00200-004-0154-8
Tanja Lange (Ed.), Open problems in implementation and application, Tech. Report D.VAM.6, revision 1.4, ECRYPT, European Network of Excellence in Cryptology, 2006.
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Dino Lorenzini, An invitation to arithmetic geometry, Graduate Studies in Mathematics, vol. 9, American Mathematical Society, Providence, RI, 1996. MR 1376367, DOI 10.1090/gsm/009
Kazuto Matsuo, Jinhui Chao, and Shigeo Tsujii, An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 461–474. MR 2041104, DOI 10.1007/3-540-45455-1_{3}6
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
Jean Francois Mestre, Algorithme pour compter des points de courbes en petite caractéristique et petit genre, 2002, lecture notes, http://www.institut.math.jussieu.fr/~mestre/rennescrypto.ps.
Peter L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), no. 170, 519–521. MR 777282, DOI 10.1090/S0025-5718-1985-0777282-X
National Institute of Standards and Technology, Digital Signature Standard, FIPS Publication 186-2, 2000.
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
J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247–270. MR 1801221
C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, DOI 10.1090/S0025-5718-1984-0744939-5
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
Benjamin Smith, Isogenies and the discrete logarithm problem on Jacobians of genus $3$ hyperelliptic curves, Cryptology ePrint Archive, Report 2007/428, 2007, http://eprint.iacr.org/.
Richard Stallman et al., GNU compiler collection 4.1.2, February 2007, http://gcc.gnu.org/index.html.
Andreas Stein and Edlyn Teske, Explicit bounds and heuristics on class numbers in hyperelliptic function fields, Math. Comp. 71 (2002), no. 238, 837–861. MR 1885633, DOI 10.1090/S0025-5718-01-01385-0
Andrew V. Sutherland, Order computations in generic groups, Ph.D. thesis, Massachusetts Institute of Technology, 2007, http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf.
Edlyn Teske, A space efficient algorithm for group structure computation, Math. Comp. 67 (1998), no. 224, 1637–1663. MR 1474658, DOI 10.1090/S0025-5718-98-00968-5
Edlyn Teske, The Pohlig-Hellman method generalized for group structure computation, J. Symbolic Comput. 27 (1999), no. 6, 521–534. MR 1701092, DOI 10.1006/jsco.1999.0279
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}
Nicolas Thériault, Weil descent attack for Kummer extensions, J. Ramanujan Math. Soc. 18 (2003), no. 3, 281–312. MR 2007146
Frederik Vercauteren, Computing zeta functions of curves over finite fields, Ph.D. thesis, Katholieke Universiteit Leuven, 2003.
André Weil, Numbers of solutions of equations in finite fields, Bull. Amer. Math. Soc. 55 (1949), 497–508. MR 29393, DOI 10.1090/S0002-9904-1949-09219-4
Annegret Weng, A class of hyperelliptic CM-curves of genus three, J. Ramanujan Math. Soc. 16 (2001), no. 4, 339–372. MR 1877806
Annegret Weng, Constructing hyperelliptic curves of genus 2 suitable for cryptography, Math. Comp. 72 (2003), no. 241, 435–458. MR 1933830, DOI 10.1090/S0025-5718-02-01422-9
Thomas Wollinger, Software and hardware implementation of hyperelliptic curve cryptosystems, Ph.D. thesis, Ruhr-University of Bochum, 2004.