I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.
First, some background on Quadratic Residues:
A Quadratic Residue (QR) is a number $x$ such that there exists some number $y$ with $x \equiv y^2 \pmod p$ (where $p$ is the modulus we're talking about - I'll make it implicit here on out), and it doesn't matter what $y$ is, only that whether such a $y$ exists.
There exists an efficient test where we can determine whether any value $x$ is a QR or not.
The value $x \times y$ is q QR if either both $x, y$ are QRs, or neither is. If one is a QR and the other is not, then $x \times y$ will not be.
The value $x^n$ is QR if either $x$ is a QR or $n$ is even (or both) - if $x$ is not a QR and $n$ is odd, then $x^n$ will not be a QR either.
With that in mind, the El Gamal encryption of a message $m$ is the pair:
$$(g^r, h^r \times m)$$
where $g$ is publicly known generator, $h$ is the public key (which we assume that the attacker knows, and which will be $g$ raised to some unknown power), and $r$ is a random number selected by the encryptor (and hence unknown).
What we do is determine whether $h^r$ is a QR or not (which might sound a bit tricky, as we don't know the value of $h^r$, and so we can't use our efficient test). However, we can deduce it based on the following cases:
- If $h$ is a QR, then $h^r$ will be as well.
- If $h$ is not a QR, that implies $g$ is not a QR either (because $h$ is $g$ raised to some power). In this case, we check if $g^r$ is a QR or not - if it is, then $r$ is even (and so $h^r$ is a QR). If $g^r$ is not a QR, then $r$ is odd (and so $h^r$ is not a QR).
Once we have determined that, we then check if $h^r \times m$ is a QR. If the QR-ness of $h^r$ and $h^r \times m$ are the same (that is, both are a QR, or neither is), then $m$ must be a QR. If they differ, $m$ must not be a QR.
Hence, in all cases, we can determine whether $m$ is a QR or not, by examining the ciphertext and the public key.