Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-23T12:06:58.479Z Has data issue: false hasContentIssue false
  • English
  • Français

Global Duality, Signature Calculus and the Discrete Logarithm Problem

Published online by Cambridge University Press:  01 February 2010

Ming-Deh Huang  and
Wayne Raskind
Ming-Deh Huang
Affiliation:
Department of Computer Science, University of Southern California, Los Angeles, CA 90089–0781, USA, [email protected]
Wayne Raskind
Affiliation:
Department of Mathematics, University of Southern California, Los Angeles, CA 90089–2532, USA, [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We develop a formalism for studying the discrete logarithm problem for the multiplicative group and for elliptic curves over finite fields by lifting the respective group to an algebraic number field and using global duality. One of our main tools is the signature of a Dirichlet character (in the multiplicative group case) or principal homogeneous space (in the elliptic curve case), which is a measure of its ramification at certain places. We then develop signature calculus, which generalizes and refines the index calculus method. Finally, using some heuristics, we show the random polynomial time equivalence for these two cases between the problem of computing signatures and the discrete logarithm problem. This relates the discrete logarithm problem to some very well-known problems in algebraic number theory and arithmetic geometry.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 12 , 2009 , pp. 228 - 263
Copyright
Copyright © London Mathematical Society 2009

References

1.Bektermirov, B., Mazur, B., Stein, W. and Watkins, M., ‘Average ranks of elliptic curves: tension between data and conjectures’, Bull. American Math. Society 44 (2007) 233–254CrossRefGoogle Scholar
2.Berkovich, V., ‘Duality theorems in Galois cohomology of commutative algebraic groups’, Selected translations. Selecta Math. Soviet 6 (1987), no. 3, 201–296Google Scholar
3.Cassels, J.W.S. and Fröhlich, A., Algebraic Number Theory (Academic Press 1967).Google Scholar
4.Chevalley, C., ‘Une démonstration d'un théorème sur les groupes algébriques’, J. Mathématiques Pures et Appliquées 39 (1960) 307–317Google Scholar
5.Cohen, H. and Lenstra, H.W. Jr., ‘Heuristics on class groups of number fields’, Number theory, Noordwijkerhout 1983, 33–62, Lecture Notes in Math., 1068 (Springer, Berlin, 1984).CrossRefGoogle Scholar
6.Cohen, H. and Lenstra, H.W. Jr., ‘Heuristics on class groups’, Number theory (New York, 1982), Lecture Notes in Math., 1052 (Springer, Berlin, 1984) 26–36.Google Scholar
7.Conrad, B., A modern proof of Chevalley's theorem on algebraic groups, J. Ramanujan Math. Soc. 17 (2002), no. 1, 1–18.Google Scholar
8.Darmon, H., ‘Integration on ℋp × ℋ and arithmetic applications’, Ann. of Math. (2) 154 (2001), no. 3, 589–639.CrossRefGoogle Scholar
9.Deuring, M., ‘Die Typen der Multiplikatorenringe elliptischer Funktionenkörper’, Abh. Math. Sem. Hansischen Univ. 14 (1941) 197–272.CrossRefGoogle Scholar
10.Frey, G., ‘Applications of arithmetical geometry to cryptographic constructions’, Proceedings of the Fifth International Conference on Finite Fields and Applications (Springer Verlag, 1999) 128–161.CrossRefGoogle Scholar
11.Frey, G. and Rück, H.-G., ‘A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves’, Mathematics of Computation, 62(206) (1994) 865–874.Google Scholar
12.Goldfeld, D., ‘Conjectures on elliptic curves over quadratic fields’, in Number Theory (Carbondale, Ill., 1979), Lecture Notes in Math. 751 (Springer, Berlin, 1979) 108–118.CrossRefGoogle Scholar
13.Hartshorne, R., Algebraic Geometry, Graduate Texts in Mathematics, Volume 52 (Springer-Verlag, New York, Heidelberg, Berlin 1977).CrossRefGoogle Scholar
14.Heath-Brown, D.R., ‘The average analytic rank of elliptic curves’, Duke Math. J. 122 (2004), no. 3, 591–623.CrossRefGoogle Scholar
15.Huang, M.-D., Kueh, K. L., and Tan, K.-S. ‘Lifting elliptic curves and solving the elliptic curve discrete logarithm problem’, ANTS IV, Lecture Notes in Computer Science, 1838 (Springer-Verlag, 2000).Google Scholar
16.Huang, M.-D. and Raskind, W., ‘Signature calculus and discrete logarithm problems’, Proceedings of the 7th Algorithmic Number Theory Symposium (ANTS 2006), LNCS 4076 (Springer-Verlag, 2006) 558–572.CrossRefGoogle Scholar
17.Jacobson, M.J., Koblitz, N., Silverman, J.H., Stein, A., and Teske, E., ‘Analysis of the Xedni calculus attack’, Design, Codes and Cryptography 20 (2000) 41–64.CrossRefGoogle Scholar
18.Kamienny, S., ‘Torsion points on elliptic curves and q-coefficients of modular forms’, Invent. Math. 109 (1992), no. 2, 221–229.CrossRefGoogle Scholar
19.Koblitz, N., ‘Elliptic curve cryptosystems’, Mathematics of Computation 48 (1987) 203–209.CrossRefGoogle Scholar
20.Koblitz, N., Menezes, A. and Vanstone, S., ‘The state of elliptic curve cryptography’, Design, Codes and Cryptography 19 (2000) 173–193.CrossRefGoogle Scholar
21.Lang, S., ‘Algebraic groups over finite fields’, Amer. J. Math. 78 (1956) 555–563.CrossRefGoogle Scholar
22.McCurley, K., ‘The discrete logarithm problem’, Cryptology and Computational Number Theory, ed. Pomerance, C., Proceedings of Symposia in Applied Mathematics, 42 (1990) 49–74.CrossRefGoogle Scholar
23.Miller, V., ‘Uses of elliptic curves in cryptography’, Advances in Cryptology: Proceedings of Crypto 85, Lecture Notes in Computer Science, 218 (Springer-Verlag, 1985) 417–426.CrossRefGoogle Scholar
24.Milne, J.S., Étale Cohomology (Princeton Mathematical Series, Volume 33, Princeton University Press, 1980).Google Scholar
25.Milne, J.S., Arithmetic Duality Theorems (Perspectives in Mathematics, Volume 1., Academic Press, 1986).Google Scholar
26.Nguyen, K., Thesis, Universität Essen, 2001.Google Scholar
27.Rubin, K. and Silverberg, A., ‘Ranks of elliptic curves’, Bull. Amer. Math. Soc. (N.S.) 39 (2002), no. 4, 455–474.CrossRefGoogle Scholar
28.Schirokauer, O., Weber, D., and Denny, T., ‘Discrete logarithms: The effectiveness of the index calculus method’, ANTS II, volume 1122 of Lecture Notes in Computer Science, ed. Cohen, H. (Springer-Verlag, 1996) 337–362.Google Scholar
29.Schmidt, A., ‘Rings of integers of type K (π, 1)’, Documenta Mathematica 12 (2007) 441–471.CrossRefGoogle Scholar
30.Schoof, R., ‘Counting points on elliptic curves over finite fields’, Journal de Théorie des Nombres de Bordeaux 7 (1995) 219–254.CrossRefGoogle Scholar
31.Serre, J.-P., Corps Locaux Paris Hermann 1962; English translation: Local Fields, Graduate Texts in Mathematics, Volume 67, Springer Verlag, Heidelberg-New York, 1979.Google Scholar
32.Serre, J.-P., Groupes p-divisibles (d'aprés J. Tate) (Séminaire Bourbaki 1966/67, Exposé 318, reprinted by the Société Mathématique de France, 1995).Google Scholar
33.Serre, J.-P., Groupes Algébriques et Corps de Classes Hermann, Paris, 1975. English Translation Algebraic Groups and Class Fields, Graduate Texts in Mathematics 117, Springer Verlag, 1988.Google Scholar
34.Shimura, G., Introduction to the Arithmetic Theory of Automorphic Functions (Princeton University Press, 1994).Google Scholar
35.Shimura, G., ‘Class fields over real quadratic fields and Hecke operators’, Ann. Math. 95 (1972) 130–190.CrossRefGoogle Scholar
36.Silverman, J.H., The Arithmetic of Elliptic Curves (Graduate Texts in Mathematics, Volume 106, Springer Verlag, 1986).CrossRefGoogle Scholar