# CDH between two groups implies weakness of El-Gamal

Let $G$ a cyclic group of prime order $p$ with a generator $g$.

Let $H$ a cyclic group of prime order $p$ with a generator $h$.

Suppose that you have an algorithm $\mathcal{A}$ that given two elements $g^a$ and $g^b$ in $G$ outputs $h^{ab}$ in the group $H$.

Show that El-Gamal encryption is not secure in the sense of ciphertext-indistinguishabiliy.

Let $a$ the secret key and $(g,g^a)$ the public key.

I observed that if we can control $H$, we can take $H=G$ and $h=g^a$ and we can actually decode an encryption using $\mathcal{A}$.

So, given an encryption $(g^b,g^{ab}m)$ we can run $\mathcal{A}(g,g^b)=h^{1\cdot b}=(g^a)^b=g^{ab}$ and using this we can easily obtain $m$.

My question

If we cannot control $H$ is it still possible? Can we use group isomorphism to prove that we can adjust $\mathcal{A}$ to deal with our choice of $H$? or maybe we can use $\mathcal{A}$ to only break ciphertext-indistinguishabiliy rather than full decryption of messages?

Let $m_0,m_1$ be our challenge messages with $m_0\neq m_1$. Let $(g,g^a)$ be the public key, $a$ be the private key and $(c_1=g^k,c_2=g^{ak}m_b)$ be the challenge ciphertext. Let $\mathcal O:G^2\to H:\mathcal O(g^a,g^b)\mapsto h^{ab}$. Assume $h$ to be known or to be defined as $\mathcal O(g,g)$.
We shall use $\mathcal O$ to build a Decisional Diffie-Hellman (DDH) oracle for the group G. As the IND-CPA security of ElGamal can only be reduced to DDH and not CDH, breaking DDH suffices to break IND-CPA security.
Let $h^a=\mathcal O(g,g^a)$ and $h^b=\mathcal O(g,g^k)$. Further let $h^{ak}=\mathcal O(g^a,g^k)$. Next compute $c'=c_2/m_0$. Return 0 iff $\mathcal O(g,c')=h^{ak}$ else return 1 as the guess for the challenge bit $b$.
So why does this work? Note how $c'=g^{ak}m_b/m_0$ which is $g^{ak}$ if $b=0$ and something else otherwise. Now $\mathcal O(g,c')$ sends this to $h^{ak}$ iff $b=0$, but as we have already computed $h^{ak}$ using the public keys, we can now make the comparison to verify our guess for $m_0$!