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

2 Answers 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.

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? –  T.B 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 ? –  T.B Apr 20 at 12:52

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<<1/\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.

share|improve this answer

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.