Equivalences between elliptic curves and real quadratic congruence function fields

Andreas Stein

Journal de théorie des nombres de Bordeaux (1997)

  • Volume: 9, Issue: 1, page 75-95
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Stein, Andreas. "Equivalences between elliptic curves and real quadratic congruence function fields." Journal de théorie des nombres de Bordeaux 9.1 (1997): 75-95. <http://eudml.org/doc/247991>.

@article{Stein1997,
abstract = {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.},
author = {Stein, Andreas},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {real quadratic congruence function field; continued fractions; reduced ideals; elliptic curves; discrete logarithm; Diffie-Hellman key exchange; discrete logarithm problem; real quadratic congruence function fields},
language = {eng},
number = {1},
pages = {75-95},
publisher = {Université Bordeaux I},
title = {Equivalences between elliptic curves and real quadratic congruence function fields},
url = {http://eudml.org/doc/247991},
volume = {9},
year = {1997},
}

TY - JOUR
AU - Stein, Andreas
TI - Equivalences between elliptic curves and real quadratic congruence function fields
JO - Journal de théorie des nombres de Bordeaux
PY - 1997
PB - Université Bordeaux I
VL - 9
IS - 1
SP - 75
EP - 95
AB - 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.
LA - eng
KW - real quadratic congruence function field; continued fractions; reduced ideals; elliptic curves; discrete logarithm; Diffie-Hellman key exchange; discrete logarithm problem; real quadratic congruence function fields
UR - http://eudml.org/doc/247991
ER -

References

top
  1. [1] C.S. AbelEin Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen. Dissertation, Universität des Saarlandes, Saarbrücken (Germany) 1994. 
  2. [2] W.W. Adams & M.J. Razar, Multiples of points on elliptic curves and continued fractions. Proc. London Math. Soc.41, 1980, 481-498. Zbl0403.14002MR591651
  3. [3] E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Math. Zeitschr.19 (1924), 153-206. Zbl50.0107.01MR1544651JFM50.0107.01
  4. [4] H. Cohen, A Course in Computation AlgebraicNumber Theory.Springer, Berlin1994. Zbl0786.11071MR1228206
  5. [5] M. Deuring, Lectures on the Theory of Algebraic Functions of One Variable. LNM314, Berlin1973. Zbl0249.14008MR344231
  6. [6] W. Diffie & M.E. Hellman, New directions in cryptography. IEEE Trans. Inform. Theory22, 6, 644-654, 1976. Zbl0435.94018MR437208
  7. [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. Zbl0693.12013MR1024565
  8. [8] A. Stein, V. Müller, & C. ThielComputing discrete logarithms in real quadratic congruence function fields of large genus. Submitted. Zbl1036.11064
  9. [9] R. Scheidler, J.A. Buchmann & H.C. Williams, A key exchange protocol using real quadratic fields. J. Cryptology7, 171-199, 1994. Zbl0816.94018MR1286662
  10. [10] R. Scheidler, A. Stein, & H.C. Williams, Key-exchange in real quadratic congruence function fields. Designs, Codes and Cryptography7, (1996), no. 1/2, 153-174. Zbl0851.94021MR1377761
  11. [11] F.K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik p. Math. Zeitschr.33 (1931), 1-32. Zbl0001.05401MR1545199JFM57.0229.02
  12. [12] R.J. SchoofQuadratic fields and factorization. Computational Methods in Number Theory (H. W. Lenstra and R. Tijdemans, eds.,). Math. Centrum Tracts155, 235-286, Part II, Amsterdam1983. Zbl0527.12003MR702519
  13. [13] D. Shanks, The Infrastructure of a Real Quadratic Field and its Applications. Proc. 1972 Number Theory Conf., Boulder, Colorado, (1972), 217-224. Zbl0334.12005MR389842
  14. [14] D. Shanks, On Gauss's Class Number Problems. Math. Comp.23 (1969), 151-163. Zbl0177.07103MR262204
  15. [15] J.H. Silverman, The Arithmetic of Elliptic Curves. Springer, New York, 1986. Zbl0585.14026MR817210
  16. [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. Zbl0925.11054
  17. [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. [18] A. Stein, Elliptic Congruence Function Fields. Proc. of ANTS II, Bordeaux, 1996, Lecture Notes in Computer Science1122, Springer (1996), 375-384. Zbl0899.11055MR1446525
  19. [19] A. Stein & H.C. Williams, Baby step Giant step in Real Quadratic Function Fields. Unpublished Manuscript. 
  20. [20] H. Stichtenoth, Algebraic Function Fields and Codes. Springer Verlag, Berlin (1993). Zbl0816.14011MR1251961
  21. [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. Zbl0757.11046MR1144788
  22. [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. Zbl0617.10005MR866124

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.