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 Free Access

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. Dan Boneh, The decision Diffie-Hellman problem, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 48–63. MR 1726060, 10.1007/BFb0054851
  • 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. Ronald Cramer and Victor Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 13–25. MR 1670952, 10.1007/BFb0055717
  • 5. Sinnou David, Points de petite hauteur sur les courbes elliptiques, J. Number Theory 64 (1997), no. 1, 104–129 (French, with English and French summaries). MR 1450488, 10.1006/jnth.1997.2100
  • 6. Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory 31 (1985), no. 4, 469–472. MR 798552, 10.1109/TIT.1985.1057074
  • 7. M. Flexor and J. Oesterlé, Sur les points de torsion des courbes elliptiques, Astérisque 183 (1990), 25–36 (French). Séminaire sur les Pinceaux de Courbes Elliptiques (Paris, 1988). MR 1065153
  • 8. Marc Hindry and Joseph Silverman, Sur le nombre de points de torsion rationnels sur une courbe elliptique, C. R. Acad. Sci. Paris Sér. I Math. 329 (1999), no. 2, 97–100 (French, with English and French summaries). MR 1710502, 10.1016/S0764-4442(99)80469-8
  • 9. Michael J. Jacobson, Neal Koblitz, Joseph H. Silverman, Andreas Stein, and Edlyn Teske, Analysis of the xedni calculus attack, Des. Codes Cryptogr. 20 (2000), no. 1, 41–64. MR 1752224, 10.1023/A:1008312401197
  • 10. Antoine Joux, A one round protocol for tripartite Diffie-Hellman, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 385–393. MR 1850619, 10.1007/10722028_23
  • 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 𝑞-coefficients of modular forms, Invent. Math. 109 (1992), no. 2, 221–229. MR 1172689, 10.1007/BF01232025
  • 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. Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193–237. MR 0434947
  • 15. D. W. Masser, Counting points of small height on elliptic curves, Bull. Soc. Math. France 117 (1989), no. 2, 247–265 (English, with French summary). MR 1015810
  • 16. Ueli M. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Advances in cryptology—CRYPTO ’94 (Santa Barbara, CA, 1994) Lecture Notes in Comput. Sci., vol. 839, Springer, Berlin, 1994, pp. 271–281. MR 1316411, 10.1007/3-540-48658-5_26
  • 17. B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33–186 (1978). MR 488287
  • 18. Loïc Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Invent. Math. 124 (1996), no. 1-3, 437–449 (French). MR 1369424, 10.1007/s002220050059
  • 19. Goro Shimura, Introduction to the arithmetic theory of automorphic functions, Publications of the Mathematical Society of Japan, No. 11. Iwanami Shoten, Publishers, Tokyo; Princeton University Press, Princeton, N.J., 1971. Kan\cflex o Memorial Lectures, No. 1. MR 0314766
  • 20. Victor Shoup, Lower bounds for discrete logarithms and related problems, Advances in cryptology—EUROCRYPT ’97 (Konstanz), Lecture Notes in Comput. Sci., vol. 1233, Springer, Berlin, 1997, pp. 256–266. MR 1603068, 10.1007/3-540-69053-0_18
  • 21. Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210
  • 22. Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368
  • 23. J. Silverman, personal communication, 24 November 2001.
  • 24. Eric R. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, Advances in cryptology—EUROCRYPT 2001 (Innsbruck), Lecture Notes in Comput. Sci., vol. 2045, Springer, Berlin, 2001, pp. 195–210. MR 1895434, 10.1007/3-540-44987-6_13

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