A key-exchange protocol using real quadratic fields (Q1335027)

The Diffie-Hellman key-exchange protocol uses exponentiation in a finite field. A new version of this protocol is introduced which uses the infrastructure of a real quadratic field. This infrastructure includes notions of primitive ideals, reduced ideals, distances of ideals and distances between ideals and real numbers. The work is unique in that it uses arithmetic in a set which is not a group, which was essential for the original protocol. To briefly describe the protocol let \({\mathcal R}\) be the set of reduced principal ideals of the maximal real quadratic order of the real quadratic number field. For \(A\) and \(B\) to exchange keys \(A\) chooses a positive integer \(a\) and computes an associated reduced ideal and an approximation to its distance from \(a\) which are sent to \(B\). \(B\) does likewise with a positive integer \(b\). With the transmitted information and their original information each party is able to generate a reduced ideal. With the exchange of at most two more bits of information the reduced ideals so calculated enable them to agree on a common ideal. The algorithms required to enable the arithmetic in \({\mathcal R}\) are discussed in detail, including a discussion of the resolution of the possible ambiguity of the ideals computed. A discussion of the security of the scheme is given as well as comments on the implementation of several examples of the scheme.