Abstract
The aim of this paper is to justify the common cryptographic practice of selecting elliptic curves using their order as the primary criterion. We can formalize this issue by asking whether the discrete log problem (dlog) has the same difficulty for all curves over a given finite field with the same order. We prove that this is essentially true by showing polynomial time random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). We do so by constructing certain expander graphs, similar to Ramanujan graphs, with elliptic curves as nodes and low degree isogenies as edges. The result is obtained from the rapid mixing of random walks on this graph. Our proof works only for curves with (nearly) the same endomorphism rings. Without this technical restriction such a dlog equivalence might be false; however, in practice the restriction may be moot, because all known polynomial time techniques for constructing equal order curves produce only curves with nearly equal endomorphism rings.
Chapter PDF
Similar content being viewed by others
Keywords
References
Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Structures Algorithms 5(2), 271–284 (1994)
Bach, E., Sorenson, J.: Explicit bounds for primes in residue classes. Math. Comp. 65(216), 1717–1735 (1996)
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic curves in cryptography. London Mathematical Society. Lecture Note Series, vol. 265. Cambridge University Press, Cambridge (2000)
Cox, D.A.: Primes of the form x2 + ny2. A Wiley-Interscience Publication. John Wiley & Sons Inc. (1989)
Davidoff, G., Sarnak, P., Valette, A.: Elementary number theory, group theory, and Ramanujan graphs. London Mathematical Society Student Texts, vol. 55. Cambridge University Press, Cambridge (2003)
Deligne, P., conjecture de weil I, L.: Inst. Hautes Études Sci. Publ. Math. 43, 273–307 (1974) (French)
Deligne, P., Serre, J.-P.: Formes modulaires de poids 1. Ann. Sci. École Norm. Sup. 7(4), 507–530 (1974); (1975) (French)
Deuring, M., Typen der, D.: Multiplikatorenringe elliptischer Funktionenkörper. Abh. Math. Sem. Hansischen Univ. 14, 197–272 (1941) (German)
Eichler, M.: Quaternäre quadratische Formen und die Riemannsche Vermutung für die Kongruenzzetafunktion. Arch. Math. 5, 355–366 (1954) (German)
Fouquet, M., Morain, F.: Isogeny volcanoes and the SEA algorithm. Algorithmic number theory, 276–291 (Sydney, 2002)
Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118–138 (1999)(electronic)
Galbraith, S.D., Hess, F., Smart, N.P.: Extending the GHS weil descent attack. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 29–44. Springer, Heidelberg (2002)
Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptology 15(1), 19–46 (2002)
Gelbart, S.S., Miller, S.D.: Riemann’s zeta function and beyond. Bull. Amer. Math. Soc (N.S.) 41(1), 59–112 (2004) (electronic)
Gross, B.H.: Heights and the special values of L-series. Number theory (Montreal, Que., 1985), 115–187 (1987)
Harkins, D., Carrel, D.: The Internet key exchange (IKE), Technical Report IETF RFC 2409 (November 1998), http://www.ietf.org/rfc/rfc2409.txt
Igusa, J.-i.: Fibre systems of Jacobian varieties. III. Fibre systems of elliptic curves, Amer. J. Math. 81, 453–476 (1959)
Ihara, Y.: Discrete subgroups of PL(2; k), Algebraic Groups and Discontinuous Subgroups. In: Proc. Sympos. Pure Math., Boulder, Colo., 1965, pp. 272–278 (1966)
Iwaniec, H.: Topics in classical automorphic forms, Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 17 (1997)
Iwaniec, H., Kowalski, E.: Analytic number theory, vol. 53. American Mathematical Society Colloquium Publications, Providence (2004)
Jerrum, M., Sinclair, A.: Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved. ACM Symposium on Theory of Computing 37, 235–243 (May 1988)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48(177), 203–209 (1987)
Kohel, D.: Endomorphism rings of elliptic curves over finite fields, University of California, Berkeley, Ph.D thesis (1996)
Lang, S.: Elliptic functions. In: Graduate Texts in Mathematics, 2nd edn., vol. 112, Springer, New York (1987), With an appendix by J. Tate
Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. of Math (2), 126(3), 649–673 (1987)
Lercier, R.: Computing isogenies in F2n. Algorithmic number theory (Talence, 1996), 197–212 (1996)
Lercier, R., Morain, F.: Algorithms for computing isogenies between elliptic curves. In: Computational perspectives on number theory, Chicago, IL, 1995, pp. 77–96 (1998)
Lubotzky, A.: Discrete groups, expanding graphs and invariant measures. In: Progress in Mathematics, vol. 125, Birkhäuser Verlag, Basel (1994)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Menezes, A.J., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory 39(5), 1639–1646 (1993)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of applied cryptography. CRC Press Series on Discrete Mathematics and its Applications. CRC Press, Boca Raton (1997); With a foreword by Ronald L. Rivest
Menezes, A., Teske, E., Weng, A.: Weak fields for ECC. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 366–386. Springer, Heidelberg (2004)
Mestre, J.-F.: La méthode des graphes. Exemples et applications. In: Proceedings of the international conference on class numbers and fundamental units of algebraic number fields, Katata, pp. 217–242 (1986) (French)
Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
Ram Murty, M.: Problems in analytic number theory, Graduate Texts in Mathematics, vol. 206. Springer, New York (2001); Readings in Mathematics
National Institute of Standards and Technology, Digital Signature Standard (DSS), Technical Report FIPS PUB 186–2 (January 2000), http://csrc.nist.gov/publications/fips/
Pizer, A.K.: Ramanujan graphs and Hecke operators. Bull. Amer. Math. Soc (N.S.) 23(1), 127–137 (1990)
Pizer, A.K.: Ramanujan graphs. In: Computational perspectives on number theory, Chicago, IL, 1995, pp. 159–178 (1998)
Rudnick, Z., Sarnak, P.: Zeros of principal L-functions and random matrix theory. Duke Math. J. 81(2), 269–322 (1996); A celebration of John F. Nash, Jr.
Sarnak, P.: Some applications of modular forms. Cambridge Tracts in Mathematics, vol. 99. Cambridge University Press, Cambridge (1990)
Serre, J.-P.: Abelian l-adic representations and elliptic curves. In: Kuyk, W., Labute, J. (eds.) McGill University lecture notes written with the collaboration, W. A. Benjamin, Inc., New York (1968)
Silverman, J.H.: The arithmetic of elliptic curves. Graduate Texts in Mathematics, vol. 106. Springer, New York (1994)
Tate, J.: Endomorphisms of abelian varieties over finite fields. Invent. Math. 2, 134–144 (1966)
Tenenbaum, G.: Introduction to analytic and probabilistic number theory. Cambridge Studies in Advanced Mathematics, vol. 46. Cambridge University Press, Cambridge (1995); Translated from the second French edition (1995) by C. B. Thomas
Teske, E.: An elliptic curve trapdoor system (extended abstract). In: High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, pp. 341–352 (2004)
Washington, L.C.: Elliptic curves, Discrete Mathematics and its Applications. Chapman & Hall/CRC (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jao, D., Miller, S.D., Venkatesan, R. (2005). Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?. In: Roy, B. (eds) Advances in Cryptology - ASIACRYPT 2005. ASIACRYPT 2005. Lecture Notes in Computer Science, vol 3788. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11593447_2
Download citation
DOI: https://doi.org/10.1007/11593447_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30684-9
Online ISBN: 978-3-540-32267-2
eBook Packages: Computer ScienceComputer Science (R0)