5
$\begingroup$

In ElGamal encryption $(g^r, g^mg^{kr})$, if the randomness $r$ is always chosen from even numbers, and the attacker knows about this, is it still provable secure?

|improve this question
$\endgroup$
  • $\begingroup$ Isn't an ElGamal ciphertext $(g^r, m\cdot g^{kr})$? $\endgroup$ – pg1989 May 21 '16 at 0:03
  • $\begingroup$ You can write any $m$ as $g^{m'}$ for some $m'$. $\endgroup$ – DrLecter May 21 '16 at 3:20
  • $\begingroup$ I could write it as Yankee Doodle Dandy too - my concern is that the OP thinks you do El-Gamal encryption by exponentiating the generator by the message. How would you even decrypt? $\endgroup$ – pg1989 May 21 '16 at 3:50
  • 2
    $\begingroup$ That's often used if you want it to be additively homomorphic - and you restrict the message space so that decryption is still efficient. It's a standard trick, so no reason to be super funny here. $\endgroup$ – DrLecter May 21 '16 at 4:23
4
$\begingroup$

Suppose that computations are done in $\mathbb{F}_p^*$ for some prime $p$. Let $c = g^m g^{kr} \bmod p$. If $r$ is even then $g^{kr}$ is a square modulo $p$. As a consequence, assuming that $g$ is a non-square modulo $p$, the Legendre symbol of $c$ modulo $p$ will leak the least significant bit of $m$: if $c^{(p-1)/2} \equiv 1 \bmod p$ then $m \bmod 2 = 0$; otherwise $m \bmod 2 = 1$.

Remark If $g$ is a generator of large prime order $q$ (as should be the case for a proper implementation of ElGamal-like encryption), choosing even values for random $r$ should not help an adversary. To see it, observe that (1) $g$ and $h := g^2 \bmod p$ generate the same group of order $q$, and (2) letting $M = g^m$ the corresponding ciphertext $(g^r, M \cdot g^{kr})$ can be rewritten as $(h^{r'}, M \cdot h^{kr'})$ where $r' = r/2 \pmod q$.

However, if $r$ is chosen at random as an even integer in $[0, q)$ then one bit of randomness is lost.

|improve this answer
$\endgroup$
  • $\begingroup$ Most real implementations will choose $g$ so that it generates the subgroup of quadratic residues, so this attack should not work in general. $\endgroup$ – pg1989 May 21 '16 at 0:04
  • $\begingroup$ @pg1989: Added a comment regarding the case of $g$ being a quadratic residue. $\endgroup$ – user94293 May 21 '16 at 1:44
  • $\begingroup$ @user94293 Thanks! Does it leak any information about $m$ in the second case? $\endgroup$ – Jan Leo May 21 '16 at 6:28
  • $\begingroup$ Let $G = \langle g \rangle$ of order $q$ and $y=g^k$. The Diffie-Hellman assumption says that triples $(g^r, g^k, g^{kr})$ and $(g^r,g^k,z)$ (with $z$ a random element in $G$) are indistinguishable. It is important to see that $M = g^m$ is an element of $G$. Hence, you can view $M\cdot g^{kr} $ as a random one-time pad encryption of $M$ in group $G$. However, this requires $g^{kr}=y^r$ being an element drawn uniformly at random in $G$; or equivalently, $r$ drawn uniformly at random in $[0,q)$. This is why I say one bit of randomness is lost if $r$ is chosen as an even value in $[0,q)$. $\endgroup$ – user94293 May 21 '16 at 14:42

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.