**Discrete Logarithms, Diffie-Hellman, and Reductions**

*Neal Koblitz and 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.

**Category / Keywords: **public-key cryptography /

**Publication Info: **Also available at http://anotherlook.ca

**Date: **received 13 Nov 2010, last revised 15 Aug 2011

**Contact author: **ajmeneze at uwaterloo ca

**Available format(s): **PDF | BibTeX Citation

**Version: **20110815:114941 (All versions of this report)

**Short URL: **ia.cr/2010/577

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]