|
Obstacles to the torsion-subgroup attack on the decision Diffie-Hellman Problem
Author(s):
Neal
Koblitz;
Alfred
J.
Menezes.
Journal:
Math. Comp.
73
(2004),
2027-2041.
MSC (2000):
Primary 94A60, 11T71, 14G50
Posted:
February 25, 2004
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
Cheng and Uchiyama show that if one is given an elliptic curve, depending on a prime  , that is defined over a number field and has certain properties, then one can solve the Decision Diffie-Hellman Problem (DDHP) in  in polynomial time. We show that it is unlikely that an elliptic curve with the desired properties exists.
References:
-
- 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
 -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
Email:
koblitz@math.washington.edu
Alfred
J.
Menezes
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada
Email:
ajmeneze@uwaterloo.ca
DOI:
10.1090/S0025-5718-04-01637-0
PII:
S 0025-5718(04)01637-0
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
Posted:
February 25, 2004
Copyright of article:
Copyright
2004,
American Mathematical Society
|
Comments: webmaster@ams.org