# Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem

Let $q$ prime number, $G$ a cyclic group with order $q$ and let $g \in G$ be a generator of $G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$ (i.e., it solves the Square-DH problem). Describe a fast (polynomial time) algorithm who takes as input the elements $g^a$,$g^b$ and gives as output the element $g^{a \cdot b}$ (namely an algorithm that solves the Computational Diffie-Hellman Problem).

• I tried to solve it but i didn't manage to conclude anywhere. – To assure we can help you to the best of our abilities… what exactly have you tried, and where exactly did you hit problems? Jul 26 '15 at 7:50
• i am confused on how to construct/find this algorithm Jul 26 '15 at 8:36
• i am confused on how to construct/find this algorithm – Now I am confused if you have a problem “constructing this algorithm” or if you´re having a problem “finding this algorithm”. (To know where you might be taking a wrong path, it would be helpfull to know what you‘ve actually tried.) Anyway… you might want to follow the hint @RobertNACIRI gave you. For example, check related Q&As right here at the Crypto.SE website: Decisional Diffie Hellman assumption. Jul 26 '15 at 11:41
• cross-posted from MSE after less than 2 minutes, and answered there $\;$
– user991
Jul 26 '15 at 14:42

This is a reduction showing that if you can compute $g^{a^2}$ given $g^a$, then you can solve the computational Diffie Hellman problem. Here is the reduction.
Let $A$ be an adversary that given $g^a$ for a random $a$, outputs $g^{a^2}$ with probability $\epsilon$. We construct $A'$ who receives $u=g^a$ and $v=g^b$ and works as follows. $A'$ runs $A$ three times on input $u$, on input $v$ and on input $u\cdot v$. If $A$ returns a correct answer each time then $A'$ will have $A=g^{a^2}$, $B=g^{b^2}$ and $C=g^{(a+b)^2}=g^{a^2 + 2ab + b^2} = g^{a^2}\cdot g^{b^2} \cdot g^{2ab}$. Thus, $A'$ outputs $\sqrt{\frac{C}{A\cdot B}}$, where the square-root is of course modulo $p$.
It remains to compute the probability with which $A'$ succeeds. Naively, we would like to say that since $A$ has to succeed on all 3 inputs, $A'$ succeeds with probability $\epsilon^3$. The problem is that the inputs given by $A'$ to $A$ are not independent. This is solved by having $A'$ choose random $r$ and $s$ in ${\mathbb Z}_p^*$ and giving $A$ the inputs $g^{ra}=u^r$, $g^{sb}=v^s$ and $u\cdot v$. This will ensure that all inputs are completely independent. Now $A'$ outputs $\sqrt{\frac{C}{A^{1/r^2}\cdot B^{1/s^2}}}$ and this will be correct with probability $\epsilon^3$.