Key-exchange in real quadratic congruence function fields
type: Item
instance of: scholarly article
title: Key-exchange in real quadratic congruence function fields
zbMATH Open document ID: 0851.94021
DOI: 10.1007/BF00125081
author: Renate Scheidler
author: Andreas Stein
author: Hugh C. Williams
published in: Designs, Codes and Cryptography
publication date: 1996-04-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11R58
Mathematics Subject Classification ID: 11R11
zbMATH DE Number: 863677
zbMATH Keywords: key exchange protocols
zbMATH Keywords: discrete logarithms
zbMATH Keywords: real quadratic congruence function fields
reviewed by: Ian Blake
MaRDI profile type: Publication
cites work: Lectures on the theory of algebraic functions of one variable
cites work: New directions in cryptography
cites work: Q5531597
cites work: A key-exchange protocol using real quadratic fields
cites work: Analytische Zahlentheorie in Körpern der Charakteristik \(p\)
cites work: Q4099715
cites work: Equivalences between elliptic curves and real quadratic congruence function fields
cites work: Q4237388
cites work: Q3990508
cites work: Q5723265
cites work: Q3784159
description: scientific article; zbMATH DE number 863677