Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms

  • Ueli M. Maurer
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


Let G be an arbitrary cyclic group with generator g and order |G| with known factorization. G could be the subgroup generated by g within a larger group H. Based on an assumption about the existence of smooth numbers in short intervals, we prove that breaking the Diffie-Hellman protocol for G and base g is equivalent to computing discrete logarithms in G to the base g when a certain side information string S of length 2 log |G| is given, where S depends only on |G| but not on the definition of G and appears to be of no help for computing discrete logarithms in G. If every prime factor p of |G| is such that one of a list of expressions in p, including p − 1 and p + 1, is smooth for an appropriate smoothness bound, then S can efficiently be constructed and therefore breaking the Diffie-Hellman protocol is equivalent to computing discrete logarithms.


Elliptic Curve Elliptic Curf Prime Divisor Discrete Logarithm Hyperelliptic Curve 
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.


  1. 1.
    L.M. Adleman and M.A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer Verlag, 1992.Google Scholar
  2. 2.
    J. Buchmann and H.C. Williams, A key-exchange system based on imaginary quadratic fields, Journal of Cryptology, vol. 1, no. 2, pp. 107–118, 1988.zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    E.R. Canfield, P. Erdös and C. Pomerance, On a problem of Oppenheim concerning “Factorisatio Numerorum”, J. Number Theory, vol. 17, pp. 1–28, 1983.zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    B. den Boer, Diffie-Hellman is as strong as discrete log for certain primes, Advances in Cryptology — CRYPTO’ 88, Lecture Notes in Computer Science, vol. 403, pp. 530–539, Berlin: Springer-Verlag, 1989.Google Scholar
  5. 5.
    W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    T. El-Gamal, A public key cryptosystem and a signature scheme based on the discrete logarithm, IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469–472, 1985.CrossRefzbMATHMathSciNetGoogle Scholar
  7. 7.
    S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. of the 18th Annual ACM Symposium on the Theory of Computing, pp. 316–329, 1986.Google Scholar
  8. 8.
    H.W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics, vol. 126, pp. 649–673, 1987.CrossRefMathSciNetGoogle Scholar
  9. 9.
    J.L. Massey, Advanced Technology Seminars Short Course Notes, Zurich, 1993, pp 6.66–6.68.Google Scholar
  10. 10.
    U.M. Maurer and Y. Yacobi, Non-interactive public-key cryptography, Advances in Cryptology — EUROCRYPT’ 91, Lecture Notes in Computer Science, Berlin: Springer-Verlag, vol. 547, pp. 498–507, 1991.Google Scholar
  11. 11.
    K.S. McCurley, A key distribution system equivalent to factoring, Journal of Cryptology, vol. 1, no. 2, pp. 95–105.Google Scholar
  12. 12.
    K.S. McCurley, The discrete logarithm problem, in Cryptology and computational number theory, C. Pomerance (ed.), Proc. of Symp. in Applied Math., vol. 42, pp. 49–74, American Mathematical Society, 1990.Google Scholar
  13. 13.
    A. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.Google Scholar
  14. 14.
    R. Peralta, A simple and fast probabilistic algorithm for computing square roots modulo a prime number, IEEE Trans. on Information Theory, vol. 32, no. 6, pp. 846–847, 1986.zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    S.C. Pohlig and M.E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, vol. 24, no. 1, pp. 106–110, 1978.zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    J.M. Pollard, Theorems on factorization and primality testing, Proceedings of the Cambridge Philosophical Society, vol. 76, pp. 521–528, 1974.zbMATHMathSciNetCrossRefGoogle Scholar
  17. 17.
    R.L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, vol. 21, no. 2, pp. 120–126, 1978.zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    H. Rück, A note on elliptic curves over finite fields, Math. Comp., vol. 49, pp. 301–304, 1987.zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    C.P. Schnorr, Efficient identification and signatures for smart cards, Advances in Cryptology — CRYPTO’ 89, Lecture Notes in Computer Science, vol. 435, pp. 239–252, Berlin: Springer-Verlag, 1990.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Ueli M. Maurer
    • 1
  1. 1.Institute for Theoretical Computer ScienceETH ZürichZürichSwitzerland

Personalised recommendations