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?
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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.
-
$\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
