Ive seen in an answer to this question here :
that If you XOR a random input with a biased input, the output is random .
What is the reason for that ? Is there a formal proof ?
thx
1
-
$\begingroup$ It is not possible to give a formal proof of an informal statement. $\endgroup$– fkraiemCommented Jun 5, 2018 at 12:02
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Let $X, Y \in \{0,1\}$ be random variables, with $\Pr[X = 0] = \Pr[X = 1] = 1/2$ and any distribution on $Y$ as long as $Y$ is independent of $X$ so that $$\Pr[Y = y \mathrel| X = x] = \Pr[Y = y]$$ for any fixed bits $x, y \in \{0,1\}$. What is the distribution on $X \oplus Y$? Let $b \in \{0,1\}$ be a fixed bit. Then
\begin{align*} \Pr[X \oplus Y = b] &= \Pr[X \oplus Y = b \mathrel| X = 0]\cdot\Pr[X = 0] \\ &\quad\quad + \Pr[X \oplus Y = b \mathrel| X = 1]\cdot\Pr[X = 1] \\ &= \Pr[0 \oplus Y = b \mathrel| X = 0]\cdot(1/2) \\ &\quad\quad + \Pr[1 \oplus Y = b \mathrel| X = 1]\cdot(1/2) \\ &= \Pr[Y = b \mathrel| X = 0]\cdot(1/2) \\ &\quad\quad + \Pr[Y = b \oplus 1 \mathrel| X = 1]\cdot(1/2) \\ &= \Pr[Y = b]\cdot(1/2) + \Pr[Y = b \oplus 1]\cdot(1/2) \\ &= (\Pr[Y = b] + \Pr[Y = b \oplus 1])\cdot(1/2) \\ &= 1/2, \end{align*}
the last equality arising because $b$ and $b \oplus 1$ are the only two possible values that $Y$ can take on, so $\Pr[Y = b] + \Pr[Y = b \oplus 1] = 1$.
answered Jun 5, 2018 at 13:07
$\begingroup$
$\endgroup$
Another way to see this (less formally, maybe helps the intuition): take a biased bit $m$, a random bit $p$, and produce $e=m\oplus p$.
$p$ is equiprobably 1 or 0; both happen with 50% probability. $e$ has thus 50% probability of being the inverse of $m$, 50% probability of being equal to $m$. So your guess of $m$, based on $e$, has 50% probability of being correct.
$\begingroup$
$\endgroup$
1
For a fixed biased input of $b$-bit, consider the function from random input to result of the XOR. That's a bijection from the set of $b$-bit strings to that same set. If follows that if random input is uniformly random on that set, then the output also is.
Therefore, if the biased input is constant or otherwise independent of random input assumed uniformly random, then the output also is uniformly random.
For a more formal proof, see Squeamish Ossifrage's answer.
-
1$\begingroup$ This of course implies that the biased input is independent of the random input, since if it is then you can assume the biased input to be fixed relative to the random distribution wlog. Nice. $\endgroup$– ThomasCommented Jun 5, 2018 at 7:05