Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

On the Complexity and Efficiency of a New Key Exchange System

  • Conference paper
  • First Online:

Abstract

In [2] Buchmann and Williams presented a new public key exchange system based on imaginary quadratic fields. While in that paper the system was described theoretically and its security was discussed in some detail nothing much was said about the practical implementation.

In this paper we discuss the practical aspects of the new system, its efficiency and implementation. In particular we study the crucial point of the method: ideal reduction. We suggest a refinement of the well known reduction method which has been implemented on a computer. We present extensive running time statistics and a detailed complexity analysis of the methods involved.

The implementation of the reduction procedure on chips is subject of future research.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. A.V. Aho, J.E. Hopcroft, J.D. Ullman,The design and analysis of computer algorithms, Addison-Wesley, Reading, Massachusetts, 1974.

    MATH  Google Scholar 

  2. J. Buchmann and H.C. Williams,A key exchange system based on imaginary quadratic fields, Journal of Cryptology1 (1989), to appear.

    Google Scholar 

  3. W. Diffie and M. Hellman,New directions in cryptography, IEEE Transactions on Information theory22 (1976), 472–492.

    Article MathSciNet  Google Scholar 

  4. S. Düllmann,Ein neues Verfahren zum öffentlichen Schlüsselaustausch, Staatsexamensarbeit, Universität Düsseldorf, 1988.

    Google Scholar 

  5. Hua Loo Keng,Introduction to number theory, Springer Verlag, Berlin and New York, 1982.

    MATH  Google Scholar 

  6. D.E. Knuth,The art of computer programming, vol. 2:Seminumerical algorithms, Addison-Wesley, Reading, Massachusetts, 2. Auflage, 1981.

    Google Scholar 

  7. N. Koblitz,A Family of Jacobians Suitable for Discrete Log Cryptosystems, to appear in: Proceedings of Crypto’88, Lecture Notes of Computer Science, Springer-Verlag.

    Google Scholar 

  8. J.C. Lagarias,Worst-Case Complexity Bounds for Algorithms in the Theory of Integral Quadratic Forms, Journal of Algorithms1 (1980), 142–186.

    Article MATH MathSciNet  Google Scholar 

  9. H.W. Lenstra, Jr.,On the calculation of regulators and class numbers of quadratic fields, London Math. Soc. Lecture Notes56 (1982), 123–150.

    Google Scholar 

  10. K.S. McCurley,A Key Distribution System equivalent to Factoring, preprint, 1987.

    Google Scholar 

  11. V. Miller,Use of Elliptic Curves in Cryptography, Advances in cryptology (Proceedings of Crypto’85), Lecture Notes in Computer Science218 (1986), Springer-Verlag, NY, 417–426.

    Google Scholar 

  12. W. Narkiewicz,Elementary and analytic theory of algebraic numbers, Warszawa, 1974.

    Google Scholar 

  13. W. Narkiewicz,Number theory, Warszawa, 1977, engl. edition 1983.

    Google Scholar 

  14. R.W.K. Odoni, V. Varadharajan and P.W. Sanders,Public Key Distribution in Matrix Rings, Electronic Letters20 (1984), 386–387.

    Article  Google Scholar 

  15. D. Shanks,Class number, a theory of factorization and genera, Proc. Symposia in Pure Mathematics20 (1971), 415–440.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. FB 10 Informatik, Universität des Saarlandes, D-6600, Saarbrücken, West Germany

    Johannes A. Buchmann & Stephan Düllmann

  2. Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada, R3T 2N2

    Hugh C. Williams

Authors
  1. Johannes A. Buchmann

    You can also search for this author inPubMed Google Scholar

  2. Stephan Düllmann

    You can also search for this author inPubMed Google Scholar

  3. Hugh C. Williams

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Philips Research Laboratory, Avenue Albert Einstein 4, B-1348, Louvain-la-Neuve, Belgium

    Jean-Jacques Quisquater

  2. ESAT Laboratory, Katholieke Universiteit Leuven, Kardinaal Mercierlaan 94, B-3001, Heverlee, Belgium

    Joos Vandewalle

Rights and permissions

Copyright information

© 1990 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Buchmann, J.A., Düllmann, S., Williams, H.C. (1990). On the Complexity and Efficiency of a New Key Exchange System. In: Quisquater, JJ., Vandewalle, J. (eds) Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46885-4_57

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp