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.


1 Answer 1


(…) 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.


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.