3
$\begingroup$

I've been doing the security proof for one of my Theorem. Basically, given $g^a$, $g^b$, $g^{cb}$, $g$ and $c$ as known values. Is the problem of computing $g^{acb^{-1}}$ equivalent to the Diffie Hellman-problem? In other words, is this easy to compute that?

My feeling is that its similar to the harder problem of the original Diffie-Hellman, which is given $g^a$, $g^b$, $g^c$ and to compute $g^{abc}$. But I couldn't come up with a reasonable proof. Could you please help?

Thanks,

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other).

If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you can compute $g^{b^{-1}}$; this is done by computing $g^{b^k}$ (which can be done with $O(\log k)$ queries to the DH oracle) with $k=q-1$ (where $q$ is the order of the group). Once you have that, you can do another query with $g^{b^{-1}}$ and $g^a$ to obtain $g^{ab^{-1}}$, and once you have that, you can then compute $g^{acb^{-1}}$ directly (as you know the value of $c$).

If you can solve your problem, then you can solve the computational Diffie-Hellman problem with two queries; given $g^a$ and $g^b$, you can first do a query with $g^1$, $g^b$ and $c=1$ (to compute $g^{b^{-1}}$), and then with $g^a$ and $g^{b^{-1}}$ and $c=1$ to compute $g^{ab}$

Improve this answer
$\endgroup$
2
  • $\begingroup$ This assumes the group's order is known. $\:$ Also, if the group's order is a composite with a small factor and $b$ is chosen to be a unit modulo it, then as far as I can see this only gives a complexity-theoretic equivalence rather than a cryptographic equivalence. $\;\;\;\;$ $\endgroup$
    – user991
    Jul 20, 2014 at 20:48
  • $\begingroup$ @RickyDemer: generally, we do Diffie-Hellman in groups of known order; if you are doing it in the RSA group, an alternative way to compute $g^{b^{-1}}$ is to do a DH with $g^b$ as the base $h$, and the two public values $h^x=h^y=g$; the Oracle will return the value $h^{xy} = g^{b^{-1}}$. As for the other direction where $b$ might not be invertable (and so $b^{-1}$ doesn't exist), we can replace $b$ with $b+i$ for known $i$; with nontrivial probability, we can find an $i$ where inverse exists; given $g^{a(b+i)}$, it's easy to recover $g^{ab}$ $\endgroup$
    – poncho
    Jul 20, 2014 at 21:40

Your Answer

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

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