You are looking at a specific version 20121029:140824 of this paper. See the latest version.

Paper 2012/609

A New Approach to Discrete Logarithm Problem with Auxiliary Inputs

Taechan Kim and Jung Hee Cheon

Abstract

Embedding an element of a finite field into auxiliary groups such as elliptic curve groups or extension fields of finite fields has been useful tool for analysis of cryptographic problems such as establishing the equivalence between the discrete logarithm problem and Diffie-Hellman problem or solving the discrete logarithm problem with auxiliary inputs (DLPwAI). Actually, Cheon's algorithm solving the DLPwAI can be regarded as a quantitative version of den Boer and Maurer. Recently, Kim showed in his dissertation that the generalization of Cheon's algorithm using embedding technique including Satoh's \cite{Sat09} is no faster than Pollard's rho algorithm when $d\nmid (p\pm 1)$. In this paper, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials. More precisely, with a polynomial $f(x)$ of degree $d$ over $\mathbf{F}_p$, the proposed algorithm shows the complexity $O\left(\sqrt{p^2/R}\log^2d\log p\right)$ group operations to recover $\alpha$ with $g, g^{\alpha}, \dots, g^{\alpha^{d}}$, where $R$ denotes the number of pairs $(x, y)\in\mathbf{F}_p\times \mathbf{F}_p$ such that $f(x)-f(y)=0$. As an example using the Dickson polynomial, we reveal $\alpha$ in $O(p^{1/3}\log^2{d}\log{p})$ group operations when $d|(p+1)$. Note that Cheon's algorithm requires $g, g^{\alpha}, \dots, g^{\alpha^{d}}, \dots, g^{\alpha^{2d}}$ as an instance for the same problem.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
discrete logarithm problemCheon's algorithmfast multipoint evaluationDickson polynomialsubstitution polynomialpoint countingabsolutely irreducible polynomial
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.