1
$\begingroup$

I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Addition: having determined if $m$ is a quadratic residue or not about halves the possibilities for $m$. If we know that $m$ is a name on the class roll, or is a dice value, that can be a useful information. $\endgroup$ – fgrieu Jan 23 '20 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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