如果您將隨機輸入與偏置輸入進行異或，則輸出是隨機的 - 為什麼？

我在這裡看到了這個問題的答案：

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

如果您將隨機輸入與有偏差的輸入進行異或，則輸出是隨機的。

這是什麼原因？有正式證明嗎？

謝謝

讓 $ X, Y \in {0,1} $ 是隨機變數，與 $ \Pr[X = 0] = \Pr[X = 1] = 1/2 $ 和任何分佈 $ Y $ 只要 $ Y $ 獨立於_ $ X $ 以便

$$ \Pr[Y = y \mathrel| X = x] = \Pr[Y = y] $$對於任何固定位 $ x, y \in {0,1} $ . 什麼是分佈 $ X \oplus Y $ ? 讓 $ b \in {0,1} $ 是一個固定的位。然後 $$ \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*} $$ 最後一個相等是因為 $ b $ 和 $ b \oplus 1 $ 是僅有的兩個可能的值 $ Y $ 可以承擔，所以 $ \Pr[Y = b] + \Pr[Y = b \oplus 1] = 1 $ .

引用自：https://crypto.stackexchange.com/questions/59793