-1
$\begingroup$

From here,

The Computational Diffie-Hellman problem: Given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (but not $x_1$ and $x_2$), find $y = g^{x_1·x_2}$.

  1. What happens if I knew one of the $x_1$, would it still be hard?
  2. Considering the CDH, is the problem still hard for $g^{x_1x_2}/g^{x_1}$ or $g^{x_1x_2}*g^{x_1}$ or even just $zg^{x_1x_2}$ for some integer $z$. (For cases when I don't know $x_1$ and $x_2$ and the other case when I do know one like $x_1$?)

My intuition for no.1 is that if it would reduce to only needing to solve $y_2 = g^{x_2}$ which is a hard discrete log problem. And we know that if CDH is hard, DL is hard [2].

$\endgroup$
  • 2
    $\begingroup$ Diffie-Hellman ​ ​ $\endgroup$ – user991 Dec 8 '16 at 2:46
2
$\begingroup$

The hardness of CDH arises from the fact that we do not know how to obtain $x$, given $g^x$, efficiently.

1) If one knows $x_1$, then one can easily compute $g^{x_1 x_2}$ by computing $y_2^{x_1} = (g^{x_2})^{x_1} = g^{x_1 x_2}$ using Square and Multiply!

2) For this case, suppose that computing $k = g^{x_1 x_2} / g^{x_1}$ wasn't hard. Then one could easily obtain $g^{x_1 x_2} = k \, y_1 = k \, g^{x_1}$ and CDH would not be hard which is a contradiction. You can make a similar argument for the other case. And similarly for $z \, g^{x_1 x_2}$ (assuming I didn't misunderstand what you asked), if we can compute this then multiplying it by $z^{-1}$ (which is easy to compute) will solve CDH.

$\endgroup$

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.