Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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,
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}$
