A key-exchange protocol using real quadratic fields. (English) Zbl 0816.94018

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.


94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11R11 Quadratic extensions
Full Text: DOI


[1] Buchmann, J. A.; Williams, H. C., A key-exchange system based on imaginary quadratic fields, J. Cryptology, 1, 107-118 (1988) · Zbl 0659.94004
[2] Buchmann, J. A.; Williams, H. C., A key-exchange system based on real quadratic fields, CRYPTO ’89 Proceedings, 335-343 (1990), Berlin: Springer-Verlag, Berlin · Zbl 0722.68043
[3] Buchmann, J. A.; Williams, H. C.; Loxton, J. H., Quadratic fields and cryptography, Number Theory and Cryptography, 9-25 (1990), Cambridge: Cambridge University Press, Cambridge · Zbl 0711.11038
[4] H. Cohen, F. Diaz y Diaz, and M. Oliver, Calculs de nombres de classes et de régulateurs de corps quadratiques en temps sous-exponentiel,Séminaire de Théorie des Nombres de Paris, 1992, to appear.
[5] Cohen, H.; Lenstra, H. W.; Jager, H., Heuristics on class groups, Number Theory, 26-36 (1984), New York: Springer-Verlag, New York · Zbl 0532.12008
[6] Cohen, H.; Lenstra, H. W.; Jager, H., Heuristics on class groups of number fields, Nuber Theory, 33-62 (1984), New York: Springer-Verlag, New York · Zbl 0558.12002
[7] Cohn, H., Advanced Number Theory (1962), New York: Dover, New York
[8] Diffie, W.; Hellman, M. E., New directions in cryptography, IEEE Trans. Inform. Theory, 22, 6, 644-654 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[9] Hua, L. K., Introduction to Number Theory (1982), New York: Springer-Verlag, New York · Zbl 0483.10001
[10] Kaplan, P., Sur le 2-groupe des classes d’idéaux des corps quadratiques, J. Reine Angew. Math., 283/284, 313-363 (1976) · Zbl 0337.12003
[11] Khinchin, A. Y., Continued Fractions (1964), Chicago: University of Chicago Press, Chicago · Zbl 0117.28601
[12] Knuth, D. E., The Art of Computer Programming, vol. 2 (1981), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0477.65002
[13] Littlewood, J. E., On the class number of the corpus \(P(\sqrt{ - k} )\), Proc. London Math. Soc., 27, 358-372 (1982)
[14] McCurley, K. S., A key distribution scheme based on factoring, J. Cryptology, 1, 95-105 (1988) · Zbl 0659.94003
[15] McCurley, K. S.; Mollin, R. A., Cryptographic key distribution and computation in class groups, Number Theory and Applications (Proc. NATO Advanced Study Institute on Number Theory and Applications, Banff, 1988), 459-479 (1989), Boston: Kluwer, Boston · Zbl 0712.11076
[16] Miller, V., Use of elliptic curves in cryptography,Proceedings of Crypto 85, 417-426 (1985), New York: Springer-Verlag, New York · Zbl 0589.94005
[17] Odoni, R. W. K.; Varadharajan, V.; Sanders, P. W., Public-key distribution in matrix rings, Electron. Lett., 20, 386-387 (1984)
[18] R. J. Schoof, Quadratic fields and factorization, inComputational Methods in Number Theory (H. W. Lenstra and R. Tijdeman, eds.), Math. Centrum Tracts, Number 155, Part II, Amsterdam, 1983, pp. 235-286. · Zbl 0527.12003
[19] D. Shanks, The infrastructure of a real quadratic field and its applications,Proc. 1972 Number Theory Conference, Boulder, CO, 1972, pp. 217-224. · Zbl 0334.12005
[20] Z. Shmuely, Composite Diffie-Hellman public-key generating systems are hard to break, Technical Report No. 356, Computer Science Department, Technion-Israel Institute of Technology, February 1985.
[21] Stephens, A. J.; Williams, H. C., Some computational results on a problem concerning powerful numbers, Math. Comp., 50, 182, 619-632 (1989) · Zbl 0642.12001
[22] Williams, H. C.; Wunderlich, M. C., On the parallel generation of the residues for the continued fraction factoring algorithm, Math. Comp., 48, 177, 405-423 (1987) · Zbl 0617.10005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.