On discrete logarithm problem

Question

The classic discrete logarithm problem is to find $x\in\Bbb Z_p$ such that we know generator $g$ of $Z_p$ and $p$ is a prime with $\frac{p-1}2$ a Sophie Germain prime and we are given $h\in\Bbb Z_p$ such that $g^x\equiv h\bmod p$ holds.

Suppose given $g^x\equiv h\bmod p$ we know how to generate $g^{x^{2^i}}\bmod p$ at every $i\in\Bbb N$ in $O((\log ip)^c)$ time at a fixed $c>0$ does it help to solve finding $x\in\Bbb Z_p$?

Also is it known how to generate $g^{x^{2^i}}\bmod p$ at every $i\in\Bbb N$ in $O((\log ip)^c)$ time at a fixed $c>0$?

Answer 1

Also is it known how to generate $g^{x^{2^i}} \bmod p$ at every $i \in \mathbb{N}$ in $O((\log ip)^c)$ time at a fixed $c>0$?

No, it is not known; that would immediately imply a polynomial-time method to solve the computational Diffie-Hellman problem, and that's better than what's currently known.

This problem is: given $p, g, g^x \bmod p, g^y \bmod p$, compute $g^{xy} \bmod p$.

Given such an Oracle, here is how we would solve it (and from here on in, everything is done $\bmod p$): first, we can compute $g^x \cdot g^y = g^{x + y}$

Then, we ask our Oracle to compute $g^{x^2}$, $g^{y^2}$, $g^{(x+y)^2}$ in $O((\log p)^c)$ time.

We then compute $g^{(x+y)^2} \cdot ( g^{x^2} \cdot g^{y^2} )^{-1} = g^{2xy}$

Then, we take the modular squareroot of $g^{2xy}$, that gives us $g^{xy}$

Every step above takes polynomial time.