XOR Uniformity Lemma

Updated 12 Aug 2026

•
Definition
- •
  if $Y$ is a random variable with any (even adversarially chosen) distribution over $\{0,1\}^n$ , and $X$ is an independent, uniform random variable over $\{0,1\}^n$ , then $Z := X \oplus Y$ is uniformly distributed over $\{0,1\}^n$ — regardless of what $Y$ 's distribution was
•
Why it matters
- •
  this single fact is the reason XOR shows up constantly in cryptography ("cryptographers only know how to XOR things together," as the joke goes) — it's exactly why the One-Time Pad and Stream Cipher work: XORing a message (arbitrary distribution) with an independent uniform key/pad produces a uniformly random ciphertext, hiding the message completely
•
Proof idea (1-bit case)
- •
  write out the joint distribution table for $X$ (uniform) and $Y$ (arbitrary, weights $p_0, p_1$ ); since they're independent, joint probabilities multiply; summing the two cases that produce $Z=0$ gives exactly $\tfrac{p_0}{2} + \tfrac{p_1}{2} = \tfrac{1}{2}$ since $p_0 + p_1 = 1$
•
Related

Linked references 3