TY - GEN
T1 - Collision of random walks and a refined analysis of attacks on the discrete logarithm problem
AU - Kijima, Shuji
AU - Montenegro, Ravi
N1 - Funding Information:
R. Montenegro—Supported by a Japan Society for Promotion of Science (JSPS) Fellowship while a guest at Kyushu University.
Publisher Copyright:
© International Association for Cryptologic Research 2015.
PY - 2015
Y1 - 2015
N2 - Some of the most efficient algorithms for finding the discrete logarithm involve pseudo-random implementations of Markov chains, with one or more “walks” proceeding until a collision occurs, i.e. some state is visited a second time. In this paper we develop a method for determining the expected time until the first collision. We use our technique to examine three methods for solving discrete-logarithm problems: Pollard’s Kangaroo, Pollard’s Rho, and a few versions of Gaudry-Schost. For the Kangaroo method we prove new and fairly precise matching upper and lower bounds. For the Rho method we prove the first rigorous non-trivial lower bound, and under a mild assumption show matching upper and lower bounds. Our Gaudry-Schost results are heuristic, but improve on the prior limited understanding of this method. We also give results for parallel versions of these algorithms.
AB - Some of the most efficient algorithms for finding the discrete logarithm involve pseudo-random implementations of Markov chains, with one or more “walks” proceeding until a collision occurs, i.e. some state is visited a second time. In this paper we develop a method for determining the expected time until the first collision. We use our technique to examine three methods for solving discrete-logarithm problems: Pollard’s Kangaroo, Pollard’s Rho, and a few versions of Gaudry-Schost. For the Kangaroo method we prove new and fairly precise matching upper and lower bounds. For the Rho method we prove the first rigorous non-trivial lower bound, and under a mild assumption show matching upper and lower bounds. Our Gaudry-Schost results are heuristic, but improve on the prior limited understanding of this method. We also give results for parallel versions of these algorithms.
UR - http://www.scopus.com/inward/record.url?scp=84925237579&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84925237579&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-46447-2_6
DO - 10.1007/978-3-662-46447-2_6
M3 - Conference contribution
AN - SCOPUS:84925237579
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 127
EP - 149
BT - Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
A2 - Katz, Jonathan
PB - Springer Verlag
T2 - 18th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2015
Y2 - 30 March 2015 through 1 April 2015
ER -