Abstract The Discrete Logarithm Problem with Auxiliary Inputs (DLPwAI) involves solving for an exponent $\alpha$ given the group elements $g, g^{\alpha}, \dots, g^{\alpha^d}$ in a cyclic group $G$ of prime order $p$. While Cheon’s 2006 algorithm provided a significant shortcut for cases where $d \mid (p \pm 1)$, generalizing this efficiency to other cases has remained a challenge. This paper introduces a new algorithmic approach for the DLPwAI that achieves a running time of $\tilde{O}(\sqrt{p/\tau_f} + d)$ group operations, where $\tau_f$ is the number of absolutely irreducible factors of the polynomial $f(x) - f(y)$. By shifting from algebraic embeddings to a collision-based strategy using fast multipoint evaluation, we provide a more flexible framework that generalizes previous results and offers new insights into the limitations of solving the DLPwAI in specific cyclotomic cases.
1. Introduction
The security of many cryptographic primitives, including Diffie-Hellman key exchange and Elliptic Curve Cryptography, rests on the hardness of the Discrete Logarithm Problem (DLP). In its standard form, an attacker is given $g$ and $g^{\alpha}$ and must find $\alpha$. However, advanced protocols—such as identity-based encryption, short signatures, and certain pairing-based constructions—often expose "auxiliary inputs" in the form of higher powers of the secret: $g, g^{\alpha}, g^{\alpha^2}, \dots, g^{\alpha^d}$.
This variant, known as the DLPwAI, is potentially easier to solve than the standard DLP. Cheon’s landmark work demonstrated that if $d$ divides $p-1$ or $p+1$, the complexity can be reduced from $O(\sqrt{p})$ to $O(\sqrt{p/d} + d)$. Despite several attempts to extend this to cases where $d$ divides cyclotomic polynomials $\Phi_k(p)$ for $k \ge 3$, researchers have struggled to beat the generic square-root complexity. This paper proposes a novel framework that decouples the problem from specific field structures, focusing instead on polynomial collisions.
2. The Proposed Algorithm
Our approach moves away from the traditional method of embedding the secret into a specific subfield. Instead, we utilize a collision-based strategy centered on a chosen polynomial $f(x) \in \mathbb{F}_p[x]$ of degree $d$. The algorithm proceeds in four primary stages:
2.1 List Generation
We construct two lists of group elements:
- List $L_1$: Elements of the form $g^{f(r_i \alpha)}$, where $r_i$ are randomly chosen values. These are computed using the available auxiliary inputs $g, g^{\alpha}, \dots, g^{\alpha^d}$.
- List $L_2$: Elements of the form $g^{f(s_j)}$, where $s_j$ are also randomly chosen.
2.2 Fast Multipoint Evaluation
To ensure the algorithm remains efficient, we must compute these lists faster than the naive $O(m \cdot d)$ time. By employing fast multipoint evaluation techniques—such as the Fast Fourier Transform (FFT) or Schönhage–Strassen multiplication in the exponent space—we can generate these lists in $\tilde{O}(m + d)$ time. This efficiency is crucial for maintaining the algorithm's advantage over generic methods.
2.3 Collision Hunting and Root Finding
A collision between the two lists occurs when $g^{f(r_i \alpha)} = g^{f(s_j)}$, which implies $f(r_i \alpha) \equiv f(s_j) \pmod{p}$. Once such a collision is identified, the attacker can solve for $\alpha$ by finding the roots of the polynomial $f(r_i x) - f(s_j)$ in the finite field $\mathbb{F}_p$. Since the degree of the polynomial is $d$, this step is computationally inexpensive.
3. Theoretical Analysis
3.1 The Role of $\tau_f$
The efficiency of this algorithm is intrinsically linked to the geometry of the polynomial $f(x)$. Specifically, the complexity is $\tilde{O}(\sqrt{p/\tau_f} + d)$, where $\tau_f$ is the number of absolutely irreducible factors of the bivariate polynomial $f(x) - f(y)$. A higher $\tau_f$ increases the probability of a "useful" collision between the two lists.
Our framework generalizes previous results:
- Case $d \mid (p-1)$: Using $f(x) = x^d$, we find $\tau_f = d$, which recovers Cheon’s $O(\sqrt{p/d} + d)$ complexity.
- Case $d \mid (p+1)$: Using Dickson polynomials, we achieve $\tau_f \approx d/2$, matching the known efficiency for this case.
3.2 Non-Uniform Birthday Problem
Because the values produced by $f(x)$ are not perfectly uniform, standard birthday problem bounds do not apply directly. We provide a rigorous analysis of the non-uniform birthday problem, proving that even with the distribution bias introduced by the polynomial evaluation, the success probability remains high (at least $1/172$ per iteration), making the attack practically viable.
4. The $k=3$ Barrier
One of the most significant contributions of this work is an explanation for why previous attempts to solve the DLPwAI for $d \mid \Phi_3(p)$ (where $\Phi_3(p) = p^2 + p + 1$) have failed. We prove that for any polynomial $f(x)$, the substitution form $f(x) - f(y)$ cannot have an absolutely irreducible cubic factor. This theoretical limit suggests that the "shortcut" available for $p \pm 1$ does not naturally extend to higher-order cyclotomic cases using this polynomial method.
5. Conclusion
We have presented a new, generalized algorithm for the DLPwAI that achieves competitive complexity by leveraging polynomial collisions and fast evaluation. While our method provides a unified view of existing attacks, it also highlights the inherent difficulty of the $k=3$ case. Future research should focus on identifying specific classes of polynomials that might yield higher $\tau_f$ values for other divisors of $p^k - 1$, potentially pushing the boundaries of the generic group model's lower bounds.
Summary updated