0
$\begingroup$

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$?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.