1
$\begingroup$

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

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ hi i just edited my post again will you please check to see if there is any mistake or misunderstanding in it ? $\endgroup$
    – mike
    Jul 11, 2020 at 3:31
  • $\begingroup$ and you should also consider $m \in Z_q$ and m is in range(0, q-1) $\endgroup$
    – mike
    Jul 11, 2020 at 3:46
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.