1
$\begingroup$

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?

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

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.

$\endgroup$
2
  • $\begingroup$ I thought there is a cryptosystem based on difficulty of the problem? $\endgroup$
    – Mr.
    Jan 20 at 20:45
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Feb 3 at 12:56

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.