Adversary for attack on one variant of ElGamal

Question

I came by the following question:

Consider the following variant of ElGamal encryption. Let $p= 2q+ 1$, let $G$ be the group of squares modulo $p$ so $G$ is a subgroup of $Z_p^*$ of order $q$, and let $g$ be a generator of $G$. The private key is $(G, q, g, x)$ and the public key is $(G, q, g, h)$, where $h = \> g^x$ and $x\in Z_q$ is chosen uniformly. To encrypt a message $m ∈ \> Z_q$, choose a uniform $r∈Z_q$, compute $c_1=g^r$ mod $p$ and $c2=h^r+m$ mod $p$, and let the ciphertext be $(c_1, c_2)$. Is this scheme CPA-secure? Prove your answer.

Here $G$ is set of all elements in $Z_p^*$ which are quadratic residue modulo $p$ and $Z_p^* \setminus G$ is set of non-quadratic residue elements .I think attacker should choose two messages in way that encryption of one be in set quadratic residues modulo $p$ i.e $G$ and one be in non-quadratic residues set i.e. $Z_p^* \setminus G$ then use this property to distinguish challange ciphertext . For example, if the attacker choose $m_0 = 0$ encryption of $m_0$ will be in set quadratic residues modulo $p$ i.e. $G$.

How should attacker choose $m_1$ to be able to calculate advantage of adversary exactly? The attacker can choose $m_1$ uniformly and with good probability encryption of it will not be in set quadratic residue but then I can't calculate exact advantage of this attacker. I want a attacker that i could calculate exact advantage.

Also we know $|G| = |Z_p^* \setminus G | = q$ but we do not know the way elements of $G$ are distributed over $Z_p^*$.

Recall: it is easy to tell whether or not an element $g∈Z_p^∗$ is a quadratic residue(simply see if $g^q= 1$ mod p).

Answer 1

How should attacker choose $m_1$ to be able to calculate advantage of adversary exactly?

Well, for $p$ prime, then precisely $q$ of the values in $(1, p-1)$ will be Quadratic Residues and the precisely $q$ will not be; furthermore, there is one value ($0$) that resides outside the group (and hence is also an impossible value for $h^r$). Hence, if he chooses $m_1$ uniformly from the range $(0, p-1)$ (and independently of the value $r$ the encryptor selects), then $h^r + m_1$ will be a random value uniformly from the range $(0, p-1)$, and hence will be either a quadratic nonresidue or 0 with probability $(q+1)/p > 0.5$.

You should be able to precisely compute the advantage from that.

Answer 2

The answer of @poncho was not an exact solution to my question so as StackExchange rules suggest I add my answer it might be helpful to someone.

We construct attacker as follow. Attacker gives $m_0 = 0$ and $m_1$ which have been chosen uniformly from $\mathbb{Z}_q$ to the challenger and get challenge ciphertext $c$. If $c$ is the quadratic residue then attacker return $b = 0$ otherwise it returns $b = 1$. Advantage of this attacker is $$Adv \geq \frac{1}{2} * 1 + \frac{1}{2} * \frac{q-1}{2q} = \frac{3q-1}{4q} .$$ So we constructed an attacker with non-negligible advantage which shows the scheme is not CPA-secure.