A new approach to the discrete logarithm problem with auxiliary inputs

作者：Cheon Jung Hee^*; Kim Taechan^*

来源：LMS Journal of Computation and Mathematics, 2016, 19(1): 1-15.

DOI：10.1112/S1461157015000303

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.

• 出版日期2016