1
$\begingroup$

Ive seen in an answer to this question here :

https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes/5889288#5889288

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

$\endgroup$
  • $\begingroup$ It is not possible to give a formal proof of an informal statement. $\endgroup$ – fkraiem Jun 5 '18 at 12:02
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 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$ – Thomas Jun 5 '18 at 7:05
1
$\begingroup$

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.

$\endgroup$

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.