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?
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.