Paper 2010/577

Discrete Logarithms, Diffie-Hellman, and Reductions

Neal Koblitz, Alfred Menezes, and Igor Shparlinski

Abstract

We consider the One-Prime-Not-p and All-Primes-But-p variants of the Discrete Logarithm (DL) problem in a group of prime order p. We give reductions to the Diffie-Hellman (DH) problem that do not depend on any unproved conjectures about smooth or prime numbers in short intervals. We show that the One-Prime-Not-p-DL problem reduces to DH in time roughly L_p(1/2); the All-Primes-But-p-DL problem reduces to DH in time roughly L_p(2/5); and the All-Primes-But-p-DL problem reduces to the DH plus Integer Factorization problems in polynomial time. We also prove that under the Riemann Hypothesis, with e*log p queries to a yes-or-no oracle one can reduce DL to DH in time roughly L_p(1/2); and under a conjecture about smooth numbers, with e*log p queries to a yes-or-no oracle one can reduce DL to DH in polynomial time.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Also available at http://anotherlook.ca
Contact author(s)
ajmeneze @ uwaterloo ca
History
2011-08-15: last of 6 revisions
2010-11-14: received
See all versions
Short URL
https://ia.cr/2010/577
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/577,
      author = {Neal Koblitz and Alfred Menezes and Igor Shparlinski},
      title = {Discrete Logarithms, Diffie-Hellman, and Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2010/577},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/577}},
      url = {https://eprint.iacr.org/2010/577}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.