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

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ related question if you're in the DH setting: crypto.stackexchange.com/q/26264/23623 $\endgroup$ – SEJPM♦ May 24 '16 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 '16 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 '16 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 '16 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 '16 at 20:07
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$

| improve this answer | |
$\endgroup$
  • $\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 '16 at 22:04
  • $\begingroup$ @chisky: if it is were possible, we now know a security reduction we didn't before... $\endgroup$ – poncho May 25 '16 at 3:07
  • $\begingroup$ @poncho is cDH is less secure than DL? $\endgroup$ – Erik Aronesty May 21 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 at 14:43

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.