International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Raminder Ruprai (#401)
Name Raminder Ruprai
Topic of his/her doctorate. Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problems and Applications
Category foundations
Keywords discrete logarithm problem cryptanalysis elliptic curve
Ph.D. Supervisor(s) Steven D. Galbraith
Year of completion 2010
Abstract The discrete logarithm problem (DLP) is a problem used throughout cryptography and information security as the bedrock of the security of many systems. The DLP applies in any group but is only considered a hard problem in certain groups. We focus on the DLP in these groups and particularly the DLP in an interval that is smaller than the order of the group. The Pollard kangaroo algorithm solves the DLP in an interval of size N with heuristic expected running time approximately 2\sqrt{N} group operations. It is wellknown that the Pollard rho method can be sped-up by using equivalence classes, but such ideas have not been used for the DLP in an interval. Pollard very recently showed how to solve the DLP in an interval with heuristic expected running time of less than 1.71\sqrt{N} group operations, using just one inversion in the group. Our two main results in this area are to give algorithms to solve the DLP in an interval of size N with heuristic expected running time of less than 1.72\sqrt{N} group operations for a generic group and 1.47\sqrt{N} group operations for groups with fast inversion. We also present an improvement to the Gaudry-Schost low-memory algorithm for solving the 2-dimensional DLP and extend this improvement to the general multidimensional DLP. The main tool of the algorithm is a multidimensional pseudorandom walk which we analyse thoroughly in the 1, 2 and 3 dimensional cases as well as giving some discussion for higher dimensions.
Last Change 2011-04-17 11:36:00
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR