|
1Department of Mathematics, Box 354350, University of Washington,
Seattle, WA
98195 U.S.A.
2Department of Combinatorics
& Optimization, University
of Waterloo,
Waterloo, Ontario
N2L 3G1 Canada
3Department
of Computing, Macquarie University, Sydney,
NSW 2109,
Australia
|
|
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 Lp(1/2);
the All-Primes-But-p-DL problem
reduces to DH in time roughly Lp(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 εlog p queries to a yes-or-no 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 yes-or-no oracle
one can reduce DL to DH in polynomial time.
|
