Skip to main content
4 of 4
question a title make
Squeamish Ossifrage
  • 49.5k
  • 3
  • 118
  • 227

Are CDH and Square-DH equally hard?

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?

T.B
  • 1.3k
  • 13
  • 24