Paper 2012/609

A NEW APPROACH TO THE DISCRETE LOGARITHM PROBLEM WITH AUXILIARY INPUTS

Taechan Kim and 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown status
Keywords
discrete logarithm problemCheon's algorithmbirthday problem
Contact author(s)
yoshiki1 @ snu ac kr
History
2014-06-04: revised
2012-10-29: received
See all versions
Short URL
https://ia.cr/2012/609
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/609,
      author = {Taechan Kim and Jung Hee Cheon},
      title = {A NEW APPROACH TO THE DISCRETE LOGARITHM PROBLEM WITH AUXILIARY INPUTS},
      howpublished = {Cryptology ePrint Archive, Paper 2012/609},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/609}},
      url = {https://eprint.iacr.org/2012/609}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.