×
Stein, Andreas

Equivalences between elliptic curves and real quadratic congruence function fields. (English) Zbl 0899.11054

J. Théor. Nombres Bordx. 9, No. 1, 75-95 (1997).
The Diffie-Hellman key exchange protocol has previously been considered in the principal ideal class of a real quadratic number field as well as real quadratic congruence function fields. This set does not possess a group structure but rather an infrastructure. The security of the scheme depends on that of the discrete logarithm problem in this setting. This article shows that the discrete logarithm problem in real quadratic congruence function fields of genus 1, called real elliptic congruence function fields, is equivalent to that for elliptic curves. The properties and arithmetic of the set of reduced principal ideals in elliptic congruence function fields are discussed. The connection between elliptic curves and real quadratic congruence function fields is made. The one-to-one correspondence between the set of reduced principal ideals of an elliptic congruence function field and the group \(\langle{\mathcal P}\rangle/\{ {\mathcal P} \}\) is made, where \({\mathcal P}\) denotes an \({\mathbb{F}}_q\)-rational point on the corresponding elliptic curve. Several questions of importance that arise in establishing this correspondence are also discussed.
Reviewer: Ian F.Blake (Palo Alto)

Cited in 6 Documents

MSC:

11R58 Arithmetic theory of algebraic function fields
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
11Y16 Number-theoretic algorithms; complexity
11G05 Elliptic curves over global fields
14H52 Elliptic curves

Keywords:

Diffie-Hellman key exchange; discrete logarithm problem; real quadratic congruence function fields; elliptic curves
Cite Review PDF
Full Text: DOI Numdam EuDML EMIS

References:

[1] Abel, C.S.Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen. Dissertation, Universität des Saarlandes, Saarbrücken (Germany) 1994.
[2] Adams, W.W. & Razar, M.J., Multiples of points on elliptic curves and continued fractions. Proc. London Math. Soc.41, 1980, 481-498. · Zbl 0403.14002
[3] Artin, E., Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Math. Zeitschr.19 (1924), 153-206. · JFM 50.0107.01
[4] Cohen, H., A Course in Computation AlgebraicNumber Theory.Springer, Berlin1994. · Zbl 0786.11071
[5] Deuring, M., Lectures on the Theory of Algebraic Functions of One Variable. 314, Berlin1973. · Zbl 0249.14008
[6] Diffie, W. & Hellman, M.E., New directions in cryptography. IEEE Trans. Inform. Theory22, 6, 644-654, 1976. · Zbl 0435.94018
[7] Friedman, E. & Washington, L.C., On the distribution of divisor class groups of curves over finite fields. Theorie des Nombres, Proc. Int. Number Theory Conf. Laval, 1987, Walter de Gruyter, Berlin and New York, 227-239, 1989. · Zbl 0693.12013
[8] Stein, A., Müller, V., & Thiel, C.Computing discrete logarithms in real quadratic congruence function fields of large genus. Submitted. · Zbl 1036.11064
[9] Scheidler, R., Buchmann, J.A. & Williams, H.C., A key exchange protocol using real quadratic fields. J. Cryptology7, 171-199, 1994. · Zbl 0816.94018
[10] Scheidler, R., Stein, A., & Williams, H.C., Key-exchange in real quadratic congruence function fields. Designs, Codes and Cryptography7, (1996), no. 1/2, 153-174. · Zbl 0851.94021
[11] Schmidt, F.K., Analytische Zahlentheorie in Körpern der Charakteristik p. Math. Zeitschr.33 (1931), 1-32. · JFM 57.0229.02
[12] Schoof, R.J.Quadratic fields and factorization. Computational Methods in Number Theory (H. W. Lenstra and R. Tijdemans, eds.,). Math. Centrum Tracts155, 235-286, Part II, Amsterdam1983. · Zbl 0527.12003
[13] Shanks, D., The Infrastructure of a Real Quadratic Field and its Applications. Proc. 1972 Number Theory Conf., Boulder, Colorado, (1972), 217-224. · Zbl 0334.12005
[14] Shanks, D., On Gauss’s Class Number Problems. Math. Comp.23 (1969), 151-163. · Zbl 0177.07103
[15] Silverman, J.H., The Arithmetic of Elliptic Curves. Springer, New York, 1986. · Zbl 0585.14026
[16] Stein, A. & Zimmer, H.G., An Algorithm for Determining the Regulator and the Fundamental Unit of a Hyperelliptic Congruence Function Field. Proc. 1991 Int. Symp. on Symbolic and Algebraic Computation, Bonn (Germany), July 15-17, ACM Press, 183-184. · Zbl 0925.11054
[17] Stein, A., Baby step-Giant step-Verfahren in reell-quadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich 2. Diplomarbeit, Universität des Saarlandes, Saarbrücken (Germany) 1992.
[18] Stein, A., Elliptic Congruence Function Fields. Proc. of ANTS II, Bordeaux, 1996, 1122, Springer (1996), 375-384. · Zbl 0899.11055
[19] Stein, A. & Williams, H.C., Baby step Giant step in Real Quadratic Function Fields. Unpublished Manuscript.
[20] Stichtenoth, H., Algebraic Function Fields and Codes. Springer Verlag, Berlin (1993). · Zbl 0816.14011
[21] Weis, B. & Zimmer, H.G., Artin’s Theorie der quadratischen Kongruenzfunktionenkörper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen. Mitt. Math. Ges. Hamburg, Sond.XII (1991), no. 2. · Zbl 0757.11046
[22] Williams, H.C. & Wunderlich, M.C., On the Parallel Generation of the Residues for the Continued Fraction Algorithm. Math. Comp.48 (1987), 405-423. · Zbl 0617.10005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.