0
$\begingroup$

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

$\endgroup$
6
  • $\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, 2015 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, 2015 at 8:28
  • $\begingroup$ i am confused on how to construct/find this algorithm $\endgroup$
    – Paris Lamp
    Jul 26, 2015 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, 2015 at 11:41
  • 1
    $\begingroup$ cross-posted from MSE after less than 2 minutes, and answered there $\;$ $\endgroup$
    – user991
    Jul 26, 2015 at 14:42

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Why the inputs of $A$' are not independent? Can't we choose a random $b$? $\endgroup$
    – kelalaka
    Nov 10, 2021 at 19:44
  • $\begingroup$ First, note that $A'$ doesn't get to choose $a$ and $b$; it receives $u$ and $v$ and has to work with that. This actually doesn't matter since $a$ and $b$ are independent and random. The problem is that $A'$ runs $A$ on $u$, $v$ and $u\cdot v$. Clearly $u$ and $v$ are independent, but $u\cdot v$ is not independent of $u$ and $v$. This is solved by rerandomizing $u$ and $v$ using $r$ and $s$, but leaving $u\cdot v$ so now all 3 elements are independent. $\endgroup$ Nov 11, 2021 at 6:48
  • $\begingroup$ I see. A and B changes but not C. That's what I missed while reading. Thanks. $\endgroup$
    – kelalaka
    Nov 11, 2021 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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