^{1}Department of Mathematics, Box 354350, University of Washington,
Seattle, WA
98195 U.S.A.
^{2}Department of Combinatorics
& Optimization, University
of Waterloo,
Waterloo, Ontario
N2L 3G1 Canada
^{3}Department
of Computing, Macquarie University, Sydney,
NSW 2109,
Australia

Abstract. We consider the
OnePrimeNotp and
AllPrimesButp variants of the Discrete Logarithm (DL) problem in a group
of prime order p. We give
reductions to the DiffieHellman (DH) problem that do not depend on any
unproved conjectures about smooth or prime numbers in short intervals. We
show that the OnePrimeNotpDL
problem reduces to DH in time roughly Lp(1/2);
the AllPrimesButpDL problem
reduces to DH in time roughly Lp(2/5);
and the AllPrimesButpDL
problem reduces to the DH plus Integer Factorization problems in polynomial
time. We also prove that under the Riemann Hypothesis, with εlog p queries to a yesorno oracle one can reduce DL to DH in time
roughly Lp(1/2); and under a
conjecture about smooth numbers, with εlog
p queries to a yesorno oracle
one can reduce DL to DH in polynomial time.
