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
    Commented Jan 17, 2021 at 11:39

1 Answer 1

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$
3
  • $\begingroup$ I thought there is a cryptosystem based on difficulty of the problem? $\endgroup$
    – Turbo
    Commented Jan 20, 2021 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
    Commented Feb 3, 2021 at 12:56
  • $\begingroup$ is it possible to say in P which is positive root and which is negative root? $\endgroup$
    – Turbo
    Commented Jan 8 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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