Key-exchange in real quadratic congruence function fields. (English) Zbl 0851.94021

Scheidler, R.; Stein, A.; Williams, Hugh C.

Des. Codes Cryptography 7, No. 1-2, 153-174 (1996).

The article analyzes a version of a discrete logrithm problem, commonly used for key exchange in cryptographic protocols, in the setting of real quadratic congruence function fields rather than the usual finite group. Let \(K/ \mathbb{F}_q\) be a quadratic congruence function field of the form \(K= \mathbb{F}_q (\sqrt {D})\) where \(D\in \mathbb{F}_q [x]\) is a squarefree polynomial of even degree whose leading coefficient is a square in \(\mathbb{F}^*\). Denote the ring of integers of \(K\) by \({\mathcal O}\). A subset \({\mathcal R}\), the reduced principal ideals, of the set of nonzero principal ideals, \({\mathcal P}\) of \({\mathcal O}\), is defined and a distance associated with its elements. The (Diffie-Hellman) protocol on the set \({\mathcal R}\) is as follows: the two communicating partners, Alice and Bob, agree on an odd prime power \(q\) and a square free polynomial \(D\in \mathbb{F}_q [x]\) which defines the real quadratic congruence function field. A reduced ideal in \({\mathcal R}\) along with its distance is publicly disclosed. Alice generates a secret ‘exponent’ \(a\in \mathbb{N}\) and computes the reduced ideal \(\alpha\) closest to the left of \(a\delta\) and transmits the ideal \(\alpha\) to Bob. Bob performs a similar task and both parties are able to compute a common reduced ideal which can be used to establish a common cryptographic key. The method is an extension of the recent system of R. Scheidler, J. A. Buchmann and H. C. Williams [J. Cryptology 7, 171-199 (1994; Zbl 0816.94018)] and eliminates several of its difficulties.
Algorithms required to implement this protocol are given and analyzed, supported by software performance characteristics. It is also shown that if the discrete logarithm problem for elliptic curves can be solved in polynomial time then the discrete logarithm problem for real quadratic congruence function fields \((\deg (D)=4)\) can also be solved in polynomial time.

Reviewer: I.F.Blake (Waterloo / Ontario)

MSC:

94A60	Cryptography
11R58	Arithmetic theory of algebraic function fields
11R11	Quadratic extensions

Keywords:

key exchange protocols; discrete logarithms; real quadratic congruence function fields

Citations:

Zbl 0816.94018

References:

[1]	C. S. Abel, Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen, Dissertation, Universität des Saarlandes, Saarbrücken (1994).
[2]	G. B. Agnew, R. C. Mullin and S. A. Vanstone, An implementation of elliptic curve cryptosystems over \(\mathbb{F}_{2^{155} } \), IEEE J. Selected Areas in Communications, Vol. 11 (1993) pp. 804-813. · doi:10.1109/49.223883
[3]	E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen I, II, Math. Zeitschr., Vol. 19 (1924) pp. 153-206. · JFM 50.0107.01 · doi:10.1007/BF01181074
[4]	H. Cohen, A Course in Computation Algebraic Number Theory, Springer, Berlin (1994).
[5]	H. Cohen and H. W. Lenstra, Heuristics on class groups, in Number Theory (H. Jager, ed.) (Noordwijkerhout, 1983), Lecture Notes in Mathematics, Springer, New York, 1052 (1984) pp. 26-36.
[6]	H. Cohen and H. W. Lenstra, Heuristics on class groups of number fields, in Number Theory (H. Jager, ed.) (Noordwijkerhout, 1983), Lecture Notes in Mathematics, Springer, New York, 1068 (1984) pp. 33-62.
[7]	M. Deuring, Lectures on the Theory of Algebraic Functions of One Variable, Lecture Notes in Mathematics, Berlin 314 (1973). · Zbl 0249.14008
[8]	W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, Vol. 22, No. 6, (1976) pp. 644-654. · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[9]	M. Eichler, Introduction to the Theory of Algebraic Numbers and Functions, Academic Press, New York (1966). · Zbl 0152.19502
[10]	E. Friedman and 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 (1989) pp. 227-239.
[11]	H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, London Math. Soc. Lec. Note Ser., Vol. 56, (1982) pp. 123-150.
[12]	R. Scheidler, J. A. Buchmann and H. C. Williams, A key exchange protocol using real quadratic fields, J. Cryptology, Vol. 7, (1994) pp. 171-199. · Zbl 0816.94018 · doi:10.1007/BF02318548
[13]	F. K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik p, Math. Zeitschr., Vol. 33 (1931) pp. 1-32. · Zbl 0001.05401 · doi:10.1007/BF01174341
[14]	R. J. Schoof, Quadratic fields and factorization, Computational Methods in Number Theory (H. W. Lenstra and R. Tijdemans, eds.), Math. Centrum Tracts, Part II, Amsterdam, 155 (1983) pp. 235-286.
[15]	D. Shanks, The infrastructure of a real quadratic field and its applications, Proc. 1972 Number Theory Conf., Boulder, Colorado (1972) pp. 217-224. · Zbl 0334.12005
[16]	A. Stein, Baby step-Giant step-Verfahren in reell-quadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich 2, Diplomarbeit, Universität des Saarlandes, Saarbrücken (1992).
[17]	A. Stein, Equivalences between Elliptic Curves and Real Quadratic Congruence Function Fields, in preparation. · Zbl 0899.11054
[18]	A. Stein and 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, ACM Press, July 15-17 (1991) pp. 183-184. · Zbl 0925.11054
[19]	B. Weis and 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., Vol. XII, No. 2 (1991) pp. 261-286. · Zbl 0757.11046
[20]	E. Weiss, Algebraic Number Theory, McGraw-Hill, New York (1963). · Zbl 0115.03601
[21]	X. Zhang, Ambiguous classes and 2-rank of class groups of quadratic function fields, J. of China University of Science and Technology, Vol. 17, No. 4, (1987) pp. 425-431. · Zbl 0643.12002