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).

  • $\begingroup$ 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? $\endgroup$
    – e-sushi
    Jul 26 '15 at 7:50
  • $\begingroup$ It's a difficult problem linked to the "Decisional Diffie Hellman assumption". Take a look over the web to learn more about this question. $\endgroup$ Jul 26 '15 at 8:28
  • $\begingroup$ i am confused on how to construct/find this algorithm $\endgroup$
    – Paris Lamp
    Jul 26 '15 at 8:36
  • $\begingroup$ 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. $\endgroup$
    – e-sushi
    Jul 26 '15 at 11:41
  • $\begingroup$ cross-posted from MSE after less than 2 minutes, and answered there $\;$ $\endgroup$
    – 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$.

We conclude that if the original problem can be solved with non-negligible probability then so can the computational Diffie-Hellman problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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