1
$\begingroup$

Assume $g$ is generator of multiplicative group modulo prime $p$.

Assume we know $g^X\bmod p$ and $g^{XY}\bmod p$ and assume we can have access to a Diffie-Hellman oracle.

Can we find $g^Y\bmod p$ in polynomial time?

If we know how to compute $g^{X^{-1}}\bmod p$ then we can use the oracle to compute $g^Y\bmod P$.

So I believe the problem reduces to computation of $g^{X^{-1}}\bmod p$ given a Diffie-Hellman oracle.

$\endgroup$
10
  • 1
    $\begingroup$ I'm not really following what you want to achive. What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?. Do you want this to show that given $g^x$ and $g^{xy}$ if we can find then this is equivalent to CDH? $\endgroup$
    – kelalaka
    Commented Feb 12, 2022 at 18:39
  • $\begingroup$ HINT: Your Diffie-Hellman oracle takes inputs $(h,h^a,h^b)$and returns $h^{ab}$. Try using $g^x$ as the first argument. $\endgroup$
    – Daniel S
    Commented Feb 12, 2022 at 19:02
  • $\begingroup$ @kelalaka I just want to find $g^Y\bmod p$ using cdh. $\endgroup$
    – Turbo
    Commented Feb 12, 2022 at 19:51
  • $\begingroup$ @daniels I don't follow but if you know the answer please write below. $\endgroup$
    – Turbo
    Commented Feb 12, 2022 at 19:52
  • $\begingroup$ Before I write the answer, can I be assured that this is not an assignment? $\endgroup$
    – Daniel S
    Commented Feb 12, 2022 at 19:53

1 Answer 1

2
$\begingroup$

We are equipped with a function which takes three inputs $\mathrm{CDH}(h,h^a,h^b)$ that returns $h^{ab}$. We call it with the inputs $\mathrm{CDH}(g^x,g,g^{xy})$. If we write $a$ for the residue mod $p-1$ such that $ax\equiv 1\pmod{p-1}$ we see that if we define $h$ to be $g^x\mod p$ then $h^a=g^{ax}=g\mod p$ and $h^y=g^{xy}\mod p$. Thus for this choice of $h$ we have $\mathrm{CDH}(g^x,g,g^{xy})=\mathrm{CDH}(h,h^a,h^y)=h^{ay}=g^{axy}=g^y\mod p$.

There is a slight wrinkle when $x$ is not invertible mod $p-1$, for in this case $y$ is not uniquely defined by $g^{xy}$. To be precise, if $\mathrm{GCD}(x,p-1)=\ell$ then all of the values $y'=y+k\ell$ for $k=1,\ldots (p-1)/\ell$ would all have $g^{xy}=g^{xy'}\mod p$ so that $g^{y'}$ would be a legitimate answer fo any of the $y'$.

Our CDH oracle may be defined in such a way as not to accept $g$ as second argument in the case where $h=g^x$ and $x$ has a common factor with $p-1$, because $g$ does not lie in $\langle h\rangle$. In such cases we can take arbitrary $\ell$th roots of $g^x$ and $g^{xy}$ and use these as the second and third arguments and proceed as before but noting the multiple possible answers.

As an amusing aside, if we have the public values and shared secret for a Diffie-Hellman exchange, but do not know the generator (i.e. we know $g^x$, $g^y$ and $g^{xy}$ but not $g$), then such an oracle can recover $g$ since $\mathrm{CDH}(g^{xy},g^x,g^y)=g$.

$\endgroup$
4
  • 1
    $\begingroup$ Nice... so we do not need to find $g^{X^{-1}}\bmod p$ at all? For computing $g^{X^{-1}}\bmod p$ you pass in $(g^X,g,g)$ which is $(h,h^{X^{-1}},h^{X^{-1}})$ to get $h^{X^{-2}}\bmod p$ which is $g^{X^{-1}}\bmod p$? $\endgroup$
    – Turbo
    Commented Feb 12, 2022 at 22:09
  • $\begingroup$ Correct. The approach of the answer is more direct, but your method also works. $\endgroup$
    – Daniel S
    Commented Feb 12, 2022 at 22:12
  • $\begingroup$ Why $g^{xy}=g^{xy'}$? How is $g^{xk\ell}=1\bmod p$ if $k\neq(p-1)$? $\endgroup$
    – Turbo
    Commented Mar 27, 2022 at 14:42
  • $\begingroup$ Does this work for elliptic curves as well? $\endgroup$
    – Turbo
    Commented Aug 19, 2023 at 1:22

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.