Discrete logarithms with auxiliary input

Auxiliary Input helps

The discrete logarithm problem with auxiliary input is defined as the problem to compute the integer $e$ given the input $(g,g^e = r,\mathcal{G})$, whereof $\mathcal{G}$ is an abelian group and $g$ is of prime order $p$ if one knows the additional input $$\left(g^{e^2},g^{e^3},...,g^{e^d}\right) \in \mathcal{G}^d$$ In [1] Jung Hee Cheon presents an algorithm which solves the problem in $\mathcal{O}(\sqrt{p/d} + \sqrt{d})$ using $$\mathcal{O}\left(\max\left(\sqrt{(p-1)/d},\sqrt{d}\right)\right)$$ space if $d | (p-1)$. The algorithm works even if the input is reduced to $(g,g^e=r,\mathcal{G},g^{e^d},d)$ only.

If $p|(p+1)$ he shows how to solve the problem given the full input in $\mathcal{O}\left(\sqrt{p/d} + d\right)$ using the same amount of space as in the case $p|(p-1)$.



In the second paper with Taechan Kim [2] they present an algorithm with a complexity that is based on a polynomial $f \in \mathbb{F}_p[x]$ of degree $d$. They can solve the problem in this case in $\mathcal{\tilde{O}}\left(\sqrt{p/\tau_f}+d\right)$ whereof $\tau_f$ is the number of irreducible factors of the polynomial $f(x)-f(y)$.

The complexity shows that there is a tradeoff. If $d$ is small, the term $\sqrt{p/d}$ dominates and if $d$ gets large the term $\sqrt{d}$ increases the complexity. The reason for this is the following: They linearize the exponent in question, $e$, via $$(\text{Eq.} 1)\;\;\;e = \zeta^{k_0 + \frac{p-1}{d}k_1} $$, whereof $\zeta$ is a generator in $\mathbb{F}^*_p$ (note $p$ is the order of the group). So $k_1 < d$ and $k_0 < \frac{p-1}{d}$. By raising Eq. 1 to the $d$-th power we get $$ e^d = \zeta^{dk_0} $$ so $k_1$ vanishes and we get $e^d = \left(\zeta^d\right)^{k_0}$. Now again, they linearize $k_0$ via $k_0 = u + mv$, whereof $m = \sqrt{(p-1)/d}$. Hence $u,v < \sqrt{(p-1)/d}$, which defines the search space and which explains the first part of the complexity stated above. The term $\sqrt{d}$ follows in a similar way for $k_1$.

# Practical Instances #

In what case can such an auxiliary input occur? Is it a realistic assumption? For the next paragraph we assume that $g$ and the group $\mathcal{G}$ are public information. Assume you have an oracle $\mathcal{O}_{\text{sqr}}$ which is defined as
\begin{equation}
r\;\text{random},\;\;g^r  \stackrel{\text{input}}{\rightarrow} \mathcal{O}_{\text{sqr}} \stackrel{\text{output}}{\rightarrow} g^{r^2}
\end{equation} i.e., it squares the existing exponent regarding the generator $g$. Access to $\mathcal{O}_{\text{sqr}}$ is enough to break the Diffie-Hellmann assumption. Given the two public key $g^x$ and $g^y$, to get $g^{xy}$, just query $\mathcal{O}_{\text{sqr}}$ with $g^x$, $g^y$ and $g^{x+y}$, then compute $$ \left( \frac{g^{(x+y)^2}}{g^{x^2}g^{y^2}}\right)^{1/2} = g^{xy} $$

But the oracle in this case is different. Lets call it $\mathcal{O}_{\text{exp}}$:
\begin{equation}
r\;\text{random},\;\;g^r  \stackrel{\text{input}}{\rightarrow} \mathcal{O}_{\text{exp}} \stackrel{\text{output}}{\rightarrow} g^{er},\;e\;\text{fixed and secret}
\end{equation}Is such an oracle $\mathcal{O}_{\text{exp}}$ realistic? Yes, kind of. Jung Hee Cheon describes several cases where such an additional input is available.
It occurs in the paper [3] by Mitsunari, Sakai, and Kasahara for a traitor tracing scheme. Their security depends on the inability to compute $g^{1/x}$ if only $(g,g^x,g^{x^2},...,g^{x^d})$ is known. However, if you can compute $x$ and if you are able to compute roots in the given group efficiently, you can also solve this kind of problem if you can solve dlp with auxiliary input.

Textbook ElGamal Encryption:

1. Public Information: Abelian group $\mathcal{G}$ of prime order $p$ with generator $g$
2. Secret Key: $x \in \mathbb{Z}_p$.
3. Public Key: $A = g^x \in \mathcal{G}$.
4. Encrypt(m = message):
1. $r \stackrel{\$}{\leftarrow} \mathbb{Z}_p$
2. ciphertext = $(R,c) = (g^r, A^rm) \in \mathcal{G}^2$
5. Decrypt(ciphertext):
1. m = $R^{-x}c \in \mathcal{G}$

Another scenario where auxiliary input can be generated is whenever we have access to an ElGamal decryption oracle.

From the public information of the ElGamal scheme an attacker already has the auxiliary input $(g,A=g^x)$. To get more auxiliary input, he can execute the following queries:

1. $(r_1,r_2) \stackrel{\$}{\leftarrow} \mathbb{Z}^2_p$
2. ciphertext := $(A^{r_1},A^{r_2}) \in \mathcal{G}^2$
3. (Query) Decrypt(ciphertext):
1.  $A^{-xr_1}A^{r_2} = g^{-x^2r_1}g^{xr_2} = t$
4.  $\left(tA^{-r_2}\right)^{-1/r_1} = g^{x^2} \in \mathcal{G}$

So after one round, he gets the auxiliary input $(g,A=g^x,A_2=g^{x^2})$. For the further auxiliary input he simply replaces $A$ by $A_2$:

1. $(r_1,r_2) \stackrel{\$}{\leftarrow} \mathbb{Z}^2_p$
2. ciphertext := $(A_2^{r_1},A_2^{r_2}) \in \mathcal{G}^2$
3. (Query) Decrypt(ciphertext):
1.  $A_2^{-xr_1}A_2^{r_2} = g^{-x^3r_1}g^{x^2r_2} = t_2$
4.  $\left(t_2A_2^{-r_2}\right)^{-1/r_1} = g^{x^3} \in \mathcal{G}$

Repeating this four steps $d$ times yields the auxiliary input $$g^{x^2},g^{x^3},...,g^{x^d}$$


[1] Jung Hee Cheon: Discrete Logarithm Problems with Auxiliary Inputs. J. Cryptology 23(3): 457-476 (2010)
[2] Taechan Kim and Jung Hee Cheon, A new approach to the discrete logarithm problem with auxiliary inputs, Cryptology ePrint Archive: Report 2012/609
[3] S. Mitsunari, R. Sakai, and M. Kasahara, A New Traitor Tracing, IEICE Trans. Fundamentals, Vol. E85-A, no. 2, pp. 481-484, 2002.