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?


You are actually quite close.

Because I'm not sure I understand the stated security notion, I will break IND-CPA security instead, you should be able to adapt the idea.

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$!


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.