Score:4

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

jp flag

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.

Score:4
ng flag

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

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.