# Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

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?

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