# Is ElGamal encryption still secure if the randomness is known to be even?

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?

• Isn't an ElGamal ciphertext $(g^r, m\cdot g^{kr})$? – pg1989 May 21 '16 at 0:03
• You can write any $m$ as $g^{m'}$ for some $m'$. – DrLecter May 21 '16 at 3:20
• 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? – pg1989 May 21 '16 at 3:50
• 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. – DrLecter May 21 '16 at 4:23

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.
• Most real implementations will choose $g$ so that it generates the subgroup of quadratic residues, so this attack should not work in general. – pg1989 May 21 '16 at 0:04
• @pg1989: Added a comment regarding the case of $g$ being a quadratic residue. – user94293 May 21 '16 at 1:44
• @user94293 Thanks! Does it leak any information about $m$ in the second case? – Jan Leo May 21 '16 at 6:28
• 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)$. – user94293 May 21 '16 at 14:42