A new approach to the discrete logarithm problem with auxiliary inputs. Issue 1 (January 2016) - Cheon, Jung Hee; Kim, Taechan
Abstract : The aim of the discrete logarithm problem with auxiliary inputs is to solve for ${\itα}$, given the elements $g, g^{{\itα}}, …, g^{{\itα}^{d}}$ of a cyclic group $G=\langle g\rangle$, of prime order $p$ . The best-known algorithm, proposed by Cheon in 2006, solves for ${\itα}$ in the case where $d\mid (p± 1)$, with a running time of $O(\sqrt{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 ${\rmΦ}_{k}(p)$ where $k\geqslant 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 $\widetilde{O}(\sqrt{p/{\itτ}_{f}}+d)$ group exponentiations, where ${\itτ}_{f}$ is the number of absolutely irreducible factors of $f(x)-f(y)$ . We note that this number is always smaller than $\widetilde{O}(p^{1/2})$ . In addition, we present an analysis of a non-uniform birthday problem.