Welcome to the resource topic for 2012/609
Title:
A NEW APPROACH TO THE DISCRETE LOGARITHM PROBLEM WITH AUXILIARY INPUTS
Authors: Taechan Kim, Jung Hee Cheon
Abstract:The discrete logarithm problem with auxiliary inputs is to solve~\alpha for given elements g, g^\alpha, \ldots, g^{\alpha^d} of a cyclic group G=\langle g \rangle of prime order~p. The best-known algorithm, proposed by Cheon in 2006, solves \alpha in the case of d | (p\pm 1) with running time of O\left( \sqrt{p/d} + d^i \right) group exponentiations~(i=1 or 1/2 depending on the sign). There have been several attempts to generalize this algorithm in the case of \Phi_k(p) for k \ge 3, but it has been shown, by Kim, Cheon and Lee, that they cannot have better complexity than the usual square root algorithms. We propose a new algorithm to solve the DLPwAI. The complexity of the algorithm is determined by a chosen polynomial f \in \F_p[x] of degree d. We show that the proposed algorithm has a running time of \widetilde O\left( \sqrt{p / \tau_f} +d \right) group exponentiations, where~\tau_f is the number of absolutely irreducible factors of f(x)-f(y). We note that it is always smaller than \widetilde O(p^{1/2}). To obtain a better complexity of the algorithm, we investigate an upper bound of \tau_f and try to find polynomials that achieve the upper bound. We can find such polynomials in the case of d|(p\pm 1). In this case, the algorithm has a running time of \widetilde O\left(\sqrt{p/d} +d \right) group operations which corresponds with the lower bound in the generic group model. On the contrary, we show that no polynomial exists that achieves the upper bound in the case of d \vert\Phi_3(p)=p^2+p+1. As an independent interest, we present an analysis of a non-uniform birthday problem. Precisely, we show that a collision occurs with a high probability after O\big( \frac{1}{ \sqrt{\sum_{k} {w_k}^2} } \big) samplings of balls, where the probability w_k of assigning balls to the bin k is arbitrary.
ePrint: https://eprint.iacr.org/2012/609
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .