# Computing $g^y\bmod p$ from $g^{y^2}\bmod p$ if Diffie-Hellman is compromised?

Given generator $$g$$ of a multiplicative group mod a prime $$p$$ the Diffie Hellman problem is to find $$g^{xy}\bmod p$$ from $$g^x\bmod p$$ and $$g^y\bmod p$$. The best way to solve this is through discrete logarithms. Assume we can do this without breaking discrete logarithms.

Then is computing $$g^z\bmod p$$ from $$g^{z^2}\bmod p$$ doable in polynomial time?

• Assume that an Oracle provide the results, then can you verify the result without knowing $z$ Jan 17 at 11:39

Then is computing $$g^z\bmod p$$ from $$g^{z^2}\bmod p$$ doable in polynomial time?

If we assume that we know the order $$q$$ of $$g$$, and that it is prime, then yes, it is feasible.

Then, we can treat members of this subgroup as an abstract group, where each member is $$g^a$$ for some $$a$$. Within this abstract group, we can perform multiplication with the Oracle, that is, given $$g^a$$ and $$g^b$$, we can compute $$g^{ab \bmod q}$$. By extension, we can perform exponentiation in polynomial time, that is, given $$g^a$$ and an integer $$c$$, we can compute $$g^{a^c \bmod q}$$. And, we can compute the additive inverse (given $$g^a$$, we can compute $$g^{-a \bmod q}$$)

We further have an equality operator on this group, that is, given $$g^a$$ and $$g^b$$, we can determine whether $$a \equiv b \pmod q$$).

These operations are sufficient to implement the Tonelli-Shanks algorithm within the abstract group; this allows us to compute square-roots in polynomial time [1], and specifically, given $$g^{z^2}$$, to recover the two square root elements $$g^z$$ and $$g^{-z}$$

[1]: Probabilistic polynomial time if $$q \equiv 1 \pmod 4$$; however the probabilistic step is to find a quadratic nonresidue, and that needs to be done only once for a specific group.

• I thought there is a cryptosystem based on difficulty of the problem?
– Mr.
Jan 20 at 20:45
• @1..: the above analysis is assuming that we have a CDH oracle; for a group where we don't have such a CDH oracle, it would appear to be a secure hard problem... Feb 3 at 12:56