A new approach to the discrete logarithm problem with auxiliary inputs

Abstract

The aim of the discrete logarithm problem with auxiliary inputs is to solve for alpha, given the elements g, g(alpha), . . . , g(alpha d) of a cyclic group G = < g >, of prime order p. The best-known algorithm, proposed by Cheon in 2006, solves for a in the case where d vertical bar (p +/- 1), with a running time of O(root p/d+d(i)) group exponentiations (i = 1 or 1/2 depending on the sign). There have been several attempts to generalize this algorithm to the case of Phi(k)(p) where k >= 3. However, it has been shown by Kim, Cheon and Lee that a better complexity cannot be achieved than that of the usual square root algorithms. We propose a new algorithm for solving the DLPwAI. We show that this algorithm has a running time of (O) over tilde(root p/tau(f) + d) group exponentiations, where tau(f) is the number of absolutely irreducible factors of f (x) - f (y). We note that this number is always smaller than (O) over tilde (p(1/2)). In addition, we present an analysis of a non-uniform birthday problem.