Home

 

Recent Issues

Volume 52

1

 

 

 

Volume 51

1

2

3

4

Volume 50

1

2

3

4

Volume 49

1

2

3

4

Volume 48

1

2

3

4

 

Past Issues

 

The Journal

Cover

Aims and Scope

Subscription Information

Editorial Board

Instructions for Author

Contact Us

 

 

 

 

 

 

 

 

 

 

 

 

 

Vietnam Journal of Mathematics 39:3 (2011) 267-285

 

Discrete Logarithms, Diffie-Hellman, and

Reductions

 

Neal Koblitz1, Alfred Menezes2, and Igor E. Shparlinski3

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.

 

 

Established by Vietnam Academy of Science and Technology & Vietnam Mathematical Society

Published by Springer since January 2013