# Give a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$

We know that if the decisional Diffie-Hellmann problem is hard then the Elgamal encryption is CPA-secure. One show that if the chosen group is $$\mathbb{Z}_p^*$$ then the decisional Diffie-Hellman problem is not hard. For instance, one realizes that $$g^{ab}$$ is a square with probability $$3/4$$ with an argument based on the parity of $$a,b$$. Therefore, it makes self to ask the following question:

Is there a CPA-attack on Elgamal when used with $$\mathbb{Z}_p^*$$?

I need some help on the way to go here. Should I try to build a distinguisher using the above fact about the Diffie-Hellman problem? Or does is just come from the algebraic structure of the group?

## 1 Answer

HINT

You already have a hint given in the problem statement:

$$g^{ab}$$ is a square with probability $$3/4$$ with an argument based on the parity of $$a,b$$.

You should start by making sure you understand why is this the case. Then, once you do that, think about what it means to break DDH: it means distinguishing things that look like $$g^c$$ for a random $$c$$ from things of the form $$g^{ab}$$ for random $$a,b$$. Given the hint above, can you find a feature that differs between these two?

• Thanks for the extended explanation of the hint. Let me see if i can exploit it – Javier Jan 28 at 17:57
• Do you think asking Alice and Bob to encrypt either the generator or 1 would suffice? Because then in the second component i get an even exponent or an odd exponent and i can test whether they are quadratic residues efficiently – Javier Jan 28 at 18:05
• Yes! That would be a good way of doing it. To make sure I got you: you ask them to encrypt either $m_0 = g^0 = 1$ or $m_1 = g^1 = g$, then the encryption you get is $g^{ab}\cdot g^i = g^{ab+i}$ for either $i=0$ or $i=1$. Then you check whether this ciphertext is a quadratic residue... and what do you do next? – Daniel Jan 28 at 18:22
• If it is quadratic residue i ouput 0, otherwise 1 – Javier Jan 28 at 18:29
• Right. Just make sure to write down precisely what is the exact success probability, which won't be negligible. Good work! – Daniel Jan 28 at 19:04