Key-exchange in real quadratic congruence function fields (Q1910429)

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 \textit{R. Scheidler}, \textit{J. A. Buchmann} and \textit{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.