# Is there any result which states that if the output of these two functions is XOR'd, the XOR'd output is pseudorandom

Let $$\mathbb{G}$$ be a group of prime order $$p$$ with generator $$g$$. Suppose that I randomly pick $$r_1,z_1 \leftarrow \mathbb{Z}_p$$ and $$r_2, z_2 \leftarrow \mathbb{Z}_p$$ and $$c \leftarrow \mathbb{G}$$. Let $$\alpha = g^{r_1z_1}g^{c}$$ and $$\beta = g^{r_2z_2}g^c$$. By the semantic security of El-Gamal encryption, both $$\alpha$$ and $$\beta$$ are indistinguishable from random numbers ... Suppose that $$\alpha$$ and $$\beta$$ are encoded using bit-strings, has there been any result that their XOR is also indistinguishable from a random number or pseudorandom? i.e. $$\alpha \oplus \beta$$ is indistinguishable from a random number.

(…) is $$\alpha\oplus\beta$$ indistinguishable from a random number?

Note that we need to convert $$\alpha$$ and $$\beta$$ to bitstrings in order to apply bitwise XOR. So really we compute $$\underline\alpha\oplus\underline\beta$$ where $$\underline\gamma$$ is is the notation for a uniquely defined representation of an arbitrary group element $$\gamma$$ as a fixed-size bitstring, and it's asked if $$\underline\alpha\oplus\underline\beta$$ is a random bitstring. The answer will depend on the representation used.

It's easy to find a clear counterexample with a familiar cryptographic group and representation, such a the subgroup of quadratic residues of the multiplicative group modulo $$(2p+1)$$, when $$p$$ is a large random Sophie Germain prime of say 1999 bits¹ and leading bits 1010, and the representation of group elements as 2000-bit bitstrings per big-endian convention. $$\underline\alpha$$ and $$\underline\beta$$ are 2000-bit bitstrings with a marked bias towards 0 in the first two bits, and there is a similar (though lower) bias in the first two bits of $$\underline\alpha\oplus\underline\beta$$.

On the other hand, if in the above we replace 1010 with 111…111 over say 200 bits², then $$\underline\alpha$$ will be indistinguishable from random except for representing an $$\alpha$$ that's a quadratic residue³. Despite this, and $$\alpha$$ and $$\beta$$ not being strictly independent⁴, I conjecture both effects are weak enough that $$\underline\alpha\oplus\underline\beta$$ is computationally indistinguishable from random.

For any representation of group elements as bitstring, we can devise another representation of the same size by applying a public efficiently computable and reversible Pseudo Random Permutation to the representation. The properties of the group remain, ElGamal encryption still works and is equally secure. And now, for any $$p$$ large enough that the DLP is hard, $$\underline\alpha\oplus\underline\beta$$ can be proven computationally indistinguishable from random using properties of the PRP.

¹ Such that ElGamal encryption is secure, which is implicit in the question.

² We may want to increase the bit size of $$p$$ slightly to compensate for the Discrete Logarithm Problem being slightly eased by $$p$$ being close to a power of two.

³ A characteristic that's efficiently testable by checking that the Legendre symbol $$\left(\frac\alpha{2p+1}\right)\,\underset{\text{def}}=\,\alpha^p\bmod(2p+1)$$ is $$+1$$

⁴ Notice that $$\alpha^{-1}\beta\bmod(2p+1)$$ is a slightly biased element of the group.