Abstract
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.
Chapter PDF
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
L.M. Adleman and M.A. Huang, Primality testing and abelian varieties over finite fields, Lecture Notes in Mathematics, vol. 1512, Springer Verlag, 1992.
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.
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.
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.
W. Diffie and M.E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, vol. 22, no. 6, pp. 644–654, 1976.
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.
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.
H.W. Lenstra, Jr., Factoring integers with elliptic curves, Annals of Mathematics, vol. 126, pp. 649–673, 1987.
J.L. Massey, Advanced Technology Seminars Short Course Notes, Zurich, 1993, pp 6.66–6.68.
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.
K.S. McCurley, A key distribution system equivalent to factoring, Journal of Cryptology, vol. 1, no. 2, pp. 95–105.
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.
A. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.
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.
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.
J.M. Pollard, Theorems on factorization and primality testing, Proceedings of the Cambridge Philosophical Society, vol. 76, pp. 521–528, 1974.
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.
H. Rück, A note on elliptic curves over finite fields, Math. Comp., vol. 49, pp. 301–304, 1987.
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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maurer, U.M. (1994). Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms. In: Desmedt, Y.G. (eds) Advances in Cryptology — CRYPTO ’94. CRYPTO 1994. Lecture Notes in Computer Science, vol 839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48658-5_26
Download citation
DOI: https://doi.org/10.1007/3-540-48658-5_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58333-2
Online ISBN: 978-3-540-48658-9
eBook Packages: Springer Book Archive