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
-
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}
}
