Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
I've got another problem with extracting square root of $CDH(U,V)^2$. If the order of $G$ is odd, then the square root of $CDH(U,V)^2$ is unique, further, can we get the $k$-th($k \ne 2$) root of $CDH(U,V)^k$ is also unique? –  Alex Jan 13 at 12:53
    
@Alex you may ask this as a new question, since it generally deals with $k$-th roots and it is not directly related to the square-DH problem as asked. In general for $k$-th roots modulo $p$ and $p$ being prime, there is the following result: If $\gcd(k,p-1)=1$ then the $k$-th roots modulo $p$ are unique. –  DrLecter Jan 13 at 14:39
    
As CDH problem and Square-DH problem are equal, Can I say that Gap-DH problem is equivalent to Square-DH problem equipped with DDH oralce ? It seems that they are equal, but I cannot find a reference to show this, can you provide me some references ? –  Alex Apr 20 at 12:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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