id: 06019478
dt: j
an: 06019478
au: Koblitz, Neal; Menezes, Alfred; Shparlinski, Igor E.
ti: Discrete logarithms, Diffie-Hellman, and reductions.
so: Vietnam J. Math. 39, No. 3, 267-285 (2011).
py: 2011
pu: Vietnamese Academy of Science and Technology, Hanoi; Vietnam Mathematical
    Society, Hanoi
la: EN
cc: 
ut: 
ci: 
li: 
ab: Summary: 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 $p$
    reduces to DH in time roughly $L_p (2/5)$; and the
    All-Primes-But-$p$-DL problem reduces $p$ 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 $L_p (1/2)$; and under a conjecture
    about smooth numbers, $p$ with $ε\log p$ queries to a yes-or-no oracle
    one can reduce DL to DH in polynomial time.
rv: