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).