Are CDH and Square-DH equally hard?

Question

CDH problem roughly says that choose $U=g^u, V=g^v$ uniformly at random from cyclic group $G$, it's hard to compute $\operatorname{CDH}(U,V)=g^{uv}$.

Square-DH problem roughly says choose $U=g^u$ uniformly at random from cyclic group $G$, it's hard to compute $Z=g^{u^2}$

If I can solve the CDH problem, then it's very clear that Square-DH problem can also be solved easily: $\operatorname{CDH}(U,U)=g^{u^2}$. While, if Square-DH problem can be solved, then we can solve CDH problem of $UV$: $$g^{{(u+v)^2}}=g^{u^2+v^2+2uv}=g^{u^2}g^{v^2}\operatorname{CDH}(U,V)^2,$$ while Square-DH problem of $U$ and $V$ can be solved. So by dividing $g^{u^2}$ and $g^{v^2}$, we get $\operatorname{CDH}(U,V)^2$，and at last, compute the square root of $\operatorname{CDH}(U,V)^2$, we get $\operatorname{CDH}(U,V)$

So, can I say that they are equal to each other?

Answer 1

Mostly.

The two problems are actually more closely equivalent in a gap model than in a non-gap model.

Square-DH clearly reduces to CDH either way, but CDH reduces to two calls to Square-DH (you have 3, but you can use $(u-v)^2$ to make it 2). This is fine if the Square-DH adversary is always right, but maybe the adversary only solves the Square-DH problem with probability $\epsilon$. The reduction doesn't know whether the adversary succeeded, so it solves CDH with probability only $\epsilon^2$.

If you get to try many times to solve CDH, you have to run the Square-DH adversary $O(2/\epsilon)$ times, and make $O(\epsilon^2)$ guesses, which is somewhat loose... unless you have a DDH oracle, like in the gap model. In that case, you can filter out wrong Square-DH attempts. The reduction is still not perfectly tight, though. It can solve the CDH problem in time $t$ Square-DH calls with a probability which is to first order $t^2\epsilon^2/2$ when $t\ll1/\epsilon$. So if your adversary is inaccurate and you don't have much time, it's still a loose reduction, but if you have $\approx 1/\epsilon$ time, it becomes tight again.

Answer 2

Yes, you have shown that these two problems are equivalent by showing reductions in both directions (which is the way to address such problems). Btw., this result is well known which holds of the order of $G$ is prime.