Welcome to the resource topic for 2010/577
Title:
Discrete Logarithms, Diffie-Hellman, and Reductions
Authors: Neal Koblitz, Alfred Menezes, 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 elog 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 elog p queries to a yes-or-no oracle one can reduce DL to DH in polynomial time.
ePrint: https://eprint.iacr.org/2010/577
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .