# Security equivalent to Diffie–Hellman problem?

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,

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}$
• 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. $\;\;\;\;$
• @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}$ Jul 20, 2014 at 21:40