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

Koblitz, Neal; Menezes, Alfred

doi:10.1090/S0025-5718-04-01637-0

Obstacles to the torsion-subgroup attack on the decision Diffie-Hellman Problem
HTML articles powered by AMS MathViewer

by Neal Koblitz and Alfred J. Menezes PDF

Math. Comp. 73 (2004), 2027-2041 Request permission

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

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.
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, DOI 10.1007/BFb0054851
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.
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, DOI 10.1007/BFb0055717
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, DOI 10.1006/jnth.1997.2100
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, DOI 10.1109/TIT.1985.1057074
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
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, DOI 10.1016/S0764-4442(99)80469-8
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, DOI 10.1023/A:1008312401197
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, DOI 10.1007/10722028_{2}3
A. Joux, K. Nguyen, Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, preprint, 2001.
S. Kamienny, Torsion points on elliptic curves and $q$-coefficients of modular forms, Invent. Math. 109 (1992), no. 2, 221–229. MR 1172689, DOI 10.1007/BF01232025
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.
Daniel Sion Kubert, Universal bounds on the torsion of elliptic curves, Proc. London Math. Soc. (3) 33 (1976), no. 2, 193–237. MR 434947, DOI 10.1112/plms/s3-33.2.193
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, DOI 10.24033/bsmf.2120
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, DOI 10.1007/3-540-48658-5_{2}6
B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33–186 (1978). With an appendix by Mazur and M. Rapoport. MR 488287, DOI 10.1007/BF02684339
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, DOI 10.1007/s002220050059
Goro Shimura, Introduction to the arithmetic theory of automorphic functions, Kanô Memorial Lectures, No. 1, Iwanami Shoten Publishers, Tokyo; Princeton University Press, Princeton, N.J., 1971. Publications of the Mathematical Society of Japan, No. 11. MR 0314766
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, DOI 10.1007/3-540-69053-0_{1}8
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368, DOI 10.1007/978-1-4612-0851-8
J. Silverman, personal communication, 24 November 2001.
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, DOI 10.1007/3-540-44987-6_{1}3