A new approach to the discrete logarithm problem with auxiliary inputs. Issue 1 (January 2016)

• Record Type: Journal Article
• Authors: Cheon, Jung Hee; Kim, Taechan
• Is Part Of: LMS journal of computation and mathematics. Volume 19:Issue 1(2016)
• Page Start: 1
• Page End: 15
• Publication Date: 2016-01
• Subjects: 68Q25 (primary), -- 11Y16 (secondary)
• DOI: 10.1112/S1461157015000303
• Languages: English
• ISSNs: 1461-1570

Abstract

Abstract : The aim of the discrete logarithm problem with auxiliary inputs is to solve for ${\it\alpha}$, given the elements $g, g^{{\it\alpha}}, \ldots, g^{{\it\alpha}^{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\alpha}$ in the case where $d\mid (p\pm 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\Phi}_{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\tau}_{f}}+d)$ group exponentiations, where ${\it\tau}_{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.