1
$\begingroup$

If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $g$ and $g^{x}$?

EDIT: My question is different from “Can we reduce Diffie-Hellman problem to “Discrete-log inversion” problem?” as in this case the adversary has the values and does not need an oracle to derive it

$\endgroup$
5
  • 1
    $\begingroup$ related question if you're in the DH setting: crypto.stackexchange.com/q/26264/23623 $\endgroup$
    – SEJPM
    May 24, 2016 at 19:59
  • 1
    $\begingroup$ If this were possible then most (all?) IBE and ABE schemes that support secret key delegation would be broken. $\endgroup$
    – Artjom B.
    May 24, 2016 at 20:03
  • $\begingroup$ Does this mean the attacker can get $g^{1/x}$ for each $g^x$ (more than one) of his choice or only for the $x$ being searched? $\endgroup$
    – SEJPM
    May 24, 2016 at 20:03
  • $\begingroup$ @SEJPM I am trying to find out if an adversary is given those value without knowing what $x$ is. And also its not for more than one but only the $x$ being searched $\endgroup$
    – chisky
    May 24, 2016 at 20:06
  • $\begingroup$ @ArtjomB. so that means the adversary will not be able to tell what the value of $x$ is? I was thinking the same thing. $\endgroup$
    – chisky
    May 24, 2016 at 20:07

1 Answer 1

5
$\begingroup$

Any group where you can derive $x$ from $g, g^x, g^{1/x}$ would also have the Discrete Log problem be equivalent to the (computational) Diffie-Hellman problem. Since this is not known to be true in general, we don't know of any general method for deriving $x$ from those values.

This equivalence is quite simple to demonstrate; if it based on the fact that solving the cDH program allows us to compute $g^{1/x}$ given $g, g^x$. So, if we assume we can recover $x$ from $g, g^x, g^{1/x}$, then we can solve the Discrete Log problem (given $g, g^x$) by first recovering $g^{1/x}$ (using our cDH Oracle), and then given $g, g^x, g^{1/x}$, recover $x$

$\endgroup$
4
  • $\begingroup$ so what I am getting from your explanation is that it will not be possible to derive $x$ from those three values right? $\endgroup$
    – chisky
    May 24, 2016 at 22:04
  • $\begingroup$ @chisky: if it is were possible, we now know a security reduction we didn't before... $\endgroup$
    – poncho
    May 25, 2016 at 3:07
  • $\begingroup$ @poncho is cDH is less secure than DL? $\endgroup$ May 21, 2020 at 14:40
  • 1
    $\begingroup$ @ErikAronesty: the CDH assumption is a stronger assumption than DL; if you have solve the DL problem, you can solve the CDH problem; however it is not known how to solve the DL problem if you have a way to solve the CDH problem. $\endgroup$
    – poncho
    May 21, 2020 at 14:43

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.