 |
| 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)$.
