Equivalences between elliptic curves and real quadratic congruence function fields
Journal de théorie des nombres de Bordeaux, Volume 9 (1997) no. 1, p. 75-95

In 1994, the well-known Diffie-Hellman key exchange protocol was for the first time implemented in a non-group based setting. Here, the underlying key space was the set of reduced principal ideals of a real quadratic number field. This set does not possess a group structure, but instead exhibits a so-called infrastructure. More recently, the scheme was extended to real quadratic congruence function fields, whose set of reduced principal ideals has a similar infrastructure. As always, the security of the protocol depends on a certain discrete logarithm problem (DLP). In this paper, we show that for real quadratic congruence function fields of genus one, i.e. elliptic congruence function fields, this DLP is equivalent to the DLP for elliptic curves over finite fields. We present the explicit corresponce between the two DLPs and prove some properties which have no analogues for real quadratic number fields. Furthermore, we show that for elliptic congruence function fields, the set of reduced principal ideals is even “closer” to a group than in the general case, but still fails to be a group.

En 1994, le célèbre protocole d'échange de clefs de Diffie-Hellman fut pour la première fois implémenté dans un cas où l'espace des clefs sous-jacent n'a pas une structure de groupe : en effet l'ensemble des idéaux réduits principaux d'un corps de nombres quadratique réel n'est pas un groupe, mais néanmoins possède ce qu'on appelle une infrastructure. Récemment, ce principe a été étendu au cas des corps quadratiques réels de fonctions sur un corps fini. Comme toujours, la sécurité du protocole dépend d'un certain problème de logarithme discret (PLD). Dans cet article, nous démontrons que pour les corps quadratiques réels de fonctions sur un corps fini et de genre un, i.e les corps de fonctions elliptiques sur un corps fini, ce PLD est équivalent au PLD pour les courbes elliptiques définies sur un corps fini. Nous explicitons ici la correspondance entre ces deux PLD, et nous prouvons certaines propriétés n'ayant pas d'analogues dans le cas des corps de nombres quadratiques réels. De plus, nous montrons même que la structure de l'ensemble des idéaux réduits principaux est plus proche de celle d'un groupe dans le cas particuliers des corps de fonctions elliptiques sur un corps fini que dans le cas général, bien que ce ne soit pas un groupe.

Classification:  11A55,  11R58,  11T71,  11Y16,  68Q25,  94A60
Keywords: real quadratic congruence function field, continued fractions, reduced ideals, elliptic curves, discrete logarithm
@article{JTNB_1997__9_1_75_0,
     author = {Stein, Andreas},
     title = {Equivalences between elliptic curves and real quadratic congruence function fields},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {9},
     number = {1},
     year = {1997},
     pages = {75-95},
     zbl = {0899.11054},
     mrnumber = {1469663},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_1997__9_1_75_0}
}
Stein, Andreas. Equivalences between elliptic curves and real quadratic congruence function fields. Journal de théorie des nombres de Bordeaux, Volume 9 (1997) no. 1, pp. 75-95. http://www.numdam.org/item/JTNB_1997__9_1_75_0/

[1] C.S. Abel Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen. Dissertation, Universität des Saarlandes, Saarbrücken (Germany) 1994.

[2] W.W. Adams & M.J. Razar, Multiples of points on elliptic curves and continued fractions. Proc. London Math. Soc. 41, 1980, 481-498. | MR 591651 | Zbl 0403.14002

[3] E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Math. Zeitschr. 19 (1924), 153-206. | JFM 50.0107.01 | MR 1544651

[4] H. Cohen, A Course in Computation Algebraic Number Theory. Springer, Berlin 1994. | MR 1228206 | Zbl 0786.11071

[5] M. Deuring, Lectures on the Theory of Algebraic Functions of One Variable. LNM 314, Berlin 1973. | MR 344231 | Zbl 0249.14008

[6] W. Diffie & M.E. Hellman, New directions in cryptography. IEEE Trans. Inform. Theory 22, 6, 644-654, 1976. | MR 437208 | Zbl 0435.94018

[7] E. Friedman & L.C. Washington, 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. | MR 1024565 | Zbl 0693.12013

[8] A. Stein, V. Müller, & C. Thiel Computing discrete logarithms in real quadratic congruence function fields of large genus. Submitted.

[9] R. Scheidler, J.A. Buchmann & H.C. Williams, A key exchange protocol using real quadratic fields. J. Cryptology 7, 171-199, 1994. | MR 1286662 | Zbl 0816.94018

[10] R. Scheidler, A. Stein, & H.C. Williams, Key-exchange in real quadratic congruence function fields. Designs, Codes and Cryptography 7, (1996), no. 1/2, 153-174. | MR 1377761 | Zbl 0851.94021

[11] F.K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik p. Math. Zeitschr. 33 (1931), 1-32. | JFM 57.0229.02 | MR 1545199 | Zbl 0001.05401

[12] R.J. Schoof Quadratic fields and factorization. Computational Methods in Number Theory (H. W. Lenstra and R. Tijdemans, eds.,). Math. Centrum Tracts 155, 235-286, Part II, Amsterdam 1983. | MR 702519 | Zbl 0527.12003

[13] D. Shanks, The Infrastructure of a Real Quadratic Field and its Applications. Proc. 1972 Number Theory Conf., Boulder, Colorado, (1972), 217-224. | MR 389842 | Zbl 0334.12005

[14] D. Shanks, On Gauss's Class Number Problems. Math. Comp. 23 (1969), 151-163. | MR 262204 | Zbl 0177.07103

[15] J.H. Silverman, The Arithmetic of Elliptic Curves. Springer, New York, 1986. | MR 817210 | Zbl 0585.14026

[16] A. Stein & H.G. Zimmer, 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] A. Stein, Baby step-Giant step-Verfahren in reell-quadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich 2. Diplomarbeit, Universität des Saarlandes, Saarbrücken (Germany) 1992.

[18] A. Stein, Elliptic Congruence Function Fields. Proc. of ANTS II, Bordeaux, 1996, Lecture Notes in Computer Science 1122, Springer (1996), 375-384. | MR 1446525 | Zbl 0899.11055

[19] A. Stein & H.C. Williams, Baby step Giant step in Real Quadratic Function Fields. Unpublished Manuscript.

[20] H. Stichtenoth, Algebraic Function Fields and Codes. Springer Verlag, Berlin (1993). | MR 1251961 | Zbl 0816.14011

[21] B. Weis & H.G. Zimmer, 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. | MR 1144788 | Zbl 0757.11046

[22] H.C. Williams & M.C. Wunderlich, On the Parallel Generation of the Residues for the Continued Fraction Algorithm. Math. Comp. 48 (1987), 405-423. | MR 866124 | Zbl 0617.10005