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

Are CDH problem and Square-DH problemequally hard?

kern kern kern so my eyes don't burn
Source Link
Squeamish Ossifrage
  • 49.5k
  • 3
  • 118
  • 227

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}$$\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: ($CDH(U,U)=g^{u^2}$)$\operatorname{CDH}(U,U)=g^{u^2}$. While, if Square-DH problem can be solved  , then we cancan solve CDH problem of $UV$: $$g^{{(u+v)^2}}=g^{u^2+v^2+2uv}=g^{u^2}g^{v^2}CDH(U,V)^2$$,$$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 So by dividing $g^{u^2}$ and $g^{v^2}$, we get $CDH(U,V)^2$$\operatorname{CDH}(U,V)^2$,and at last, compute the square root of $CDH(U,V)^2$$\operatorname{CDH}(U,V)^2$, we get $CDH(U,V)$$\operatorname{CDH}(U,V)$

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

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 CDH 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?

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?

deleted 3 characters in body; edited tags
Source Link
Cryptographeur
  • 4.3k
  • 2
  • 29
  • 40

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-DHCDH 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?

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?

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 CDH 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?

Tweeted twitter.com/#!/StackCrypto/status/415837835590373376
Source Link
T.B
  • 1.3k
  • 13
  • 24
Loading