Abstract
We show how to speed up the discrete log computations on curves having automorphisms of large order, thus generalizing the attacks on anomalous binary elliptic curves. This includes the first known attack on most of the hyperelliptic curves described in the literature.
Chapter PDF
Similar content being viewed by others
References
Accola, R.D.: Two theorems on Riemann surfaces with noncyclic automorphism groups. Proc. Amer. Math. Soc. 25, 598–602 (1970)
Adleman, L.M., DeMarrais, J., Huang, M.-D.: A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 28–40. Springer, Heidelberg (1994)
Buhler, J., Koblitz, N.: Lattice basis reduction, Jacobi sums and hyperellitic cryptosystems. Bull. Austral. Math. Soc. 58, 147–154 (1998)
Cantor, D.G.: Computing in the Jacobian of an hyperelliptic curve. Math. Comp. 48(177), 95–101 (1987)
Chao, J., Matsuda, N., Sato, J., Tsujii, S.: Efficient construction of secure hyperelliptic discrete logarithm problems of large genera. In: Proc. Symposium on Cryptography and Information Security, Fukuoka, Japan (1997)
Chen, Y.-M.J.: On the elliptic curve discrete logarithm problem (June 1999) (preprint)
Cheon, J.H., Lee, D.H., Hahn, S.G.: Elliptic curve discrete logarithms and Wieferich primes (September 1998) (preprint)
Comtet, L.: Analyse combinatoire. Presses Universitaires de France (1970)
Duursma, I., Sakurai, K.: Efficient algorithms for the jacobian variety of hyperelliptic curves y2 = xp - x + 1 over a finite field of odd characteristic p. In: Tapia-Recillas, H. (ed.) Proceedings of the ”International Conference on Coding Theory, Cryptography and Related Areas, Guanajuato, Mexico, April 1998. Lecture Notes in Comput. Sci, vol. yyy (1998)
Flajolet, P., Odlyzko, A.M.: Random mapping statistics. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 329–354. Springer, Heidelberg (1990)
Frey, G., Rück, H.-G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp. 62(206), 865–874 (1994)
Galbraith, S.D., Paulus, S., Smart, N.P.: Arithmetic on superelliptic curves (1999) (preprint)
Gallant, R., Lambert, R., Vanstone, S.: Improving the parallelized Pollard lambda search on binary anomalous curves (1998), http://www.certicom.com/chal/download/paper.ps
Gaudry, P.: A variant of the Adleman-DeMarrais-Huang algorithm and its application to small genera. Research Report LIX/RR/99/04, LIX (June 1999), Available at http://www.lix.polytechnique.fr/Labo/Pierrick.Gaudry/
Jacobson, M.J., Koblitz, N., Silverman, J.H., Stein, A., Teske, E.: Analysis of the Xedni calculus attack (February 1999) (preprint)
Kani, E., Rosen, M.: Idempotent relations and factors of Jacobians. Math. Ann. 298, 307–327 (1989)
Kim, H.J., Cheon, J., Hahn, S.: Elliptic logarithm over a finite field and the lifting to Q (September 1998) (Preprint)
Koblitz, N.: A course in number theory and cryptography. Graduate Texts in Mathematics, vol. 114. Springer, Heidelberg (1987)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48(177), 203–209 (1987)
Koblitz, N.: Hyperelliptic cryptosystems. J. of Cryptology 1, 139–150 (1989)
Koblitz, N.: A family of jacobians suitable for discrete log cryptosystems. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 94–99. Springer, Heidelberg (1990)
Koblitz, N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 279–287. Springer, Heidelberg (1992)
Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. of Math. 126(2), 649–673 (1987)
Lercier, R.: Finding good random elliptic curves for cryptosystems defined over F\(_{2^n}\). In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 379–392. Springer, Heidelberg (1997)
Lercier, R., Morain, F.: Counting the number of points on elliptic curves over finite fields: strategies and performances. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 79–94. Springer, Heidelberg (1995)
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing elliptic curves logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory IT–39(5), 1639–1646 (1993)
Menezes, A.J.: Elliptic curve public key cryptosystems. Kluwer Academic Publishers, Dordrecht (1993)
Miller, V.: Use of elliptic curves in cryptography. In: Odlyzko, A.M. (ed.) Proceedings of Advances in Cryptology – CRYPTO 1986, Santa Barbara, USA, August 11–15. Lecture Notes in Comput. Sci, vol. 263, pp. 417–426. Springer, Heidelberg (1986)
Milne, J.S.: Jacobian varieties. In: Cornell, G., Silverman, J.H. (eds.) Arithmetic Geometry, pp. 167–212. Springer, Heidelberg (1986)
Müller, V.: Fast multiplication on elliptic curves over small fields of characteristic two. J. of Cryptology 11(4), 219–234 (1998)
Mumford, D.: Tata lectures on theta II. Birkhäuser, Basel (1984)
Nakajima, S.: p-ranks and automorphism groups of algebraic curves. Trans. Amer. Math. Soc. 303(2), 595–607 (1987)
Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Inform. Theory IT–24, 106–110 (1978)
Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comp. 32(143), 918–924 (1978)
Quisquater, J.-J., Delescaille, J.-P.: How easy is collision search? application to DES. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 429–434. Springer, Heidelberg (1990)
Roquette, P.: Abschätzung der Automorphismenanzahl von Funktionenkörpern bei Primzahlcharakteristik. Math. Z. 117, 157–163 (1970)
Sakai, Y., Sakurai, K.: Design of hyperelliptic cryptosystems in small charatcteristic and a software implementation over F\(_{2^n}\). In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 80–94. Springer, Heidelberg (1998)
Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Helv. 47(1), 81–92 (1998)
Sattler, J., Schnorr, C.P.: Generating random walks in groups. Ann. Univ. Sci. Budapest. Sect. Comput. 6, 65–79 (1985)
Semaev, I.A.: Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curves in characteristic p. Math. Comp. 67(221), 353–356 (1998)
Shanks, D.: Class number, a theory of factorization, and genera. In: Proc. Symp. Pure Math., vol. 20, pp. 415–440. AMS (1971)
Silverman, J.H.: Advanced Topics in the Arithmetic of Elliptic Curves. Grad. Texts in Math, vol. 151. Springer, Heidelberg (1994)
Silverman, J.H.: The XEDNI calculus and the elliptic curve discrete logarithm problem (August 1998) (preprint)
Smart, N.: The discrete logarithm problem on elliptic curves of trace one. Preprint HP-LABS Technical Report (Number HPL-97-128). To appear in J. Cryptology (1997)
Smart, N.P.: Elliptic curve cryptosystems over small fields of odd characteristic. J. of Cryptology 12(2), 141–151 (1999)
Spallek, A.-M.: Kurven vom Geschlecht 2 und ihre Anwendung in Public-Key-Kryptosystemen. PhD thesis, Universitát Gesamthochschule Essen (July 1994)
Stein, A., Teske, E.: Catching kangaroos in function fields (March 1999) (preprint)
Stichtenoth, H.: Über die Automorphismengruppe eines algebraischen Funktionenk örpers von Primzahlcharakteristik. I. Eine Abschätzung der Ordnung der Automorphismengruppe. Arch. Math. (Basel) 24, 527–544 (1973)
Teske, E.: Speeding up Pollard’s rho method for computing discrete logarithms. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 541–554. Springer, Heidelberg (1998)
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. of Cryptology 12, 1–28 (1999)
van Wamelen, P.: Examples of genus two CM curves defined over the rationals. Math. Comp. 68(225), 307–320 (1999)
Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, p. 190. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duursma, I., Gaudry, P., Morain, F. (1999). Speeding up the Discrete Log Computation on Curves with Automorphisms. In: Lam, KY., Okamoto, E., Xing, C. (eds) Advances in Cryptology - ASIACRYPT’99. ASIACRYPT 1999. Lecture Notes in Computer Science, vol 1716. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48000-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-48000-6_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66666-0
Online ISBN: 978-3-540-48000-6
eBook Packages: Springer Book Archive