Skip to main content
1 of 4
T.B
  • 1.3k
  • 13
  • 24

CDH problem and Square-DH problem

CDH problem roughly says that choose $U=g^u, V=g^v$ uniformly at random from cyclic group $G$, it's hard to compute $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 ($CDH(U,U)=g^{u^2}$). While, if Square-DH problem can be solved , then we can solve Square-DH problem of $UV$ $$g^{{(u+v)^2}}=g^{u^2+v^2+2uv}=g^{u^2}g^{v^2}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 $CDH(U,V)^2$,and at last, compute the square root of $CDH(U,V)^2$, we get $CDH(U,V)$

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

T.B
  • 1.3k
  • 13
  • 24