Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Obstacles to the torsion-subgroup attack on the decision Diffie-Hellman Problem

Authors: Neal Koblitz and Alfred J. Menezes
Translated by:
Journal: Math. Comp. 73 (2004), 2027-2041
MSC (2000): Primary 94A60, 11T71, 14G50
Published electronically: February 25, 2004
MathSciNet review: 2059749
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Cheng and Uchiyama show that if one is given an elliptic curve, depending on a prime $p$, that is defined over a number field and has certain properties, then one can solve the Decision Diffie-Hellman Problem (DDHP) in $\mathbb{F}_p^*$ in polynomial time. We show that it is unlikely that an elliptic curve with the desired properties exists.

References [Enhancements On Off] (What's this?)

  • 1. B. den Boer, Diffie-Hellman is as strong as discrete log for certain primes, Advances in Cryptology -- CRYPTO '88, Lecture Notes in Computer Science 403 (1990), Springer-Verlag, 530-539.
  • 2. D. Boneh, The decision Diffie-Hellman problem, Algorithmic Number Theory, Proc. Third Intern. Symp., ANTS-III, Lecture Notes in Computer Science 1423 (1998), Springer-Verlag, 48-63. MR 2000k:94024
  • 3. Q. Cheng, S. Uchiyama, Nonuniform polynomial time algorithm to solve decisional Diffie-Hellman problem in finite fields under conjecture, Topics in Cryptology -- CR-RSA 2002, Lecture Notes in Computer Science 2271 (2002), Springer-Verlag, 290-299.
  • 4. R. Cramer, V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, Advances in Cryptology -- CRYPTO '98, Lecture Notes in Computer Science 1462 (1998), Springer-Verlag, 13-25. MR 99j:94041
  • 5. S. David, Pointes de petites hauteurs sur les courbes elliptiques, J. Number Theory 64 (1997), 104-129. MR 98k:11067
  • 6. T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Information Theory 31 (1985), 469-472. MR 86j:94045
  • 7. M. Flexor, J. Oesterlé, Sur les points de torsion des courbes elliptiques, Astérisque 183 (1990), 25-36. MR 91g:11057
  • 8. M. Hindry, J. Silverman, Sur le nombre de points de torsion rationnels sur une courbe elliptique, C. R. Acad. Sci. Paris 329 (1999), 97-100. MR 2000g:11047
  • 9. M. Jacobson, N. Koblitz, J. Silverman, A. Stein, E. Teske, Analysis of the xedni calculus attack, Designs, Codes and Cryptography 20 (2000), 41-64. MR 2001b:14043
  • 10. A. Joux, A one round protocol for tripartite Diffie-Hellman, Algorithmic Number Theory, Proc. Third Intern. Symp., ANTS-IV, Lecture Notes in Computer Science 1838 (2000), Springer-Verlag, 385-393. MR 2002i:14029
  • 11. A. Joux, K. Nguyen, Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, preprint, 2001.
  • 12. S. Kamienny, Torsion points on elliptic curves and $q$-coefficients of modular forms, Invent. Math. 109 (1992), 221-229. MR 93h:11054
  • 13. N. Koblitz, A tale of three equations; or the emperors have no clothes, The Mathematical Intelligencer 10 (1988), 4-11; and: Reply to unclad emperors, ibid., 14-16.
  • 14. D. Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), 193-237. MR 55:7910
  • 15. D. Masser, Counting small points on elliptic curves, Bull. Soc. Math. France 117 (1989), 247-265. MR 90k:11068
  • 16. U. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Advances in Cryptology -- CRYPTO '94, Lecture Notes in Computer Science 839 (1994), Springer-Verlag, 271-281. MR 95k:94021
  • 17. B. Mazur, Modular curves and the Eisenstein ideal, Publ. Math. Inst. Hautes Études Sci. 47 (1978), 33-186. MR 80c:14015
  • 18. L. Merel, Borne pour la torsion des courbes elliptiques sur les corps des nombres, Invent. Math. 124 (1996), 437-449. MR 96i:11057
  • 19. G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton Univ. Press, 1971. MR 47:3318
  • 20. V. Shoup, ``Lower bounds for discrete logarithms and related problems'', Advances in Cryptology -- EUROCRYPT '97, Lecture Notes in Computer Science 1233 (1997), Springer-Verlag, 256-266. MR 98j:94023
  • 21. J. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, 1986. MR 87g:11070
  • 22. J. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Springer-Verlag, 1994. MR 96b:11074
  • 23. J. Silverman, personal communication, 24 November 2001.
  • 24. E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, Advances in Cryptology -- EUROCRYPT 2001, Lecture Notes in Computer Science 2045 (2001), Springer-Verlag, 195-210. MR 2003b:94062

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 94A60, 11T71, 14G50

Retrieve articles in all journals with MSC (2000): 94A60, 11T71, 14G50

Additional Information

Neal Koblitz
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195

Alfred J. Menezes
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada

Keywords: Discrete logarithm, Diffie-Hellman Problem, elliptic curve, torsion point, modular curve
Received by editor(s): May 29, 2002
Received by editor(s) in revised form: May 3, 2003
Published electronically: February 25, 2004
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society