Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not.
Is $z = x \oplus y$ uniform?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Yes, if $x$ and $y$ are chosen independently of each other.
One way to quickly see this is to note that the map $x \mapsto x \oplus y,$ for some constant $y,$ is a permutation of $\{0,1\}^n.$ This means that if $x$ is uniformly distributed over $\{0,1\}^n$ and $y$ is constant, then $x \oplus y$ is also uniformly distributed. And since $x \oplus y$ is uniformly distributed for every constant $y,$ it follows that, if we make $y$ itself a random variable (independent of $x$), then the distribution of $x \oplus y$ will be a mixture of uniform distributions, and thus uniform.
Or we can just do the math:
$$\begin{aligned} {\rm P}(x \oplus y = a) &= \sum_{b \in \{0,1\}^n} {\rm P}(x \oplus y = a \land y = b) \\ &= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b \land y = b) \\ &= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b)\ {\rm P}(y = b) & (x \perp y) \\ &= \sum_{b \in \{0,1\}^n} \frac1{2^n}\ {\rm P}(y = b) & (x \sim \mathcal U\{0,1\}^n) \\ &= \frac1{2^n} \sum_{b \in \{0,1\}^n} {\rm P}(y = b) \\ &= \frac1{2^n}. \end{aligned}$$
However, the assumption of independence is absolutely necessary here — without it, it's easy to come up with counterexamples, such as letting $x$ be uniformly distributed over $\{0,1\}^n$ and letting $y = x,$ which of course implies that $x \oplus y = 0^n.$
