# Adversary for attack on one variant of ElGamal

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

• What does the notation " $m_0=0~$ encryption of..." mean? – kodlu Jul 10 at 20:37
• @kodlu Im not sure .somebody edited question this way.what i meat was encryption of $m_0 = 0$ will be in set quadratic residue – mike Jul 11 at 2:52

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$$.
• and you should also consider $m \in Z_q$ and m is in range(0, q-1) – mike Jul 11 at 3:46
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.