Three XOR-Lemmas - An Exposition
Oded Goldreich
Abstract: We provide an exposition of three Lemmas which relate general properties of distributions with the exclusive-or of certain bit locations. The first XOR-Lemma, commonly attributed to U.V. Vazirani, relates the statistical distance of a distribution from uniform to the maximum bias of the xor of certain bit positions. The second XOR-Lemma, due to U.V. Vazirani and V.V. Vazirani, is a computational analogue of the first. It relates the pseudorandomness of a distribution with the difficulty of predicting the xor of bits in particular or random positions. The third Lemma, due to Goldreich and Levin, relates the difficulty of retrieving a string and the unpredictability of the xor of random bit positions. (The most notable XOR Lemma - that is the so-called Yao XOR Lemma is not discussed here.) The proofs presented here differ from the proofs presented in the original works. Furthermore, these proofs are believed to be simpler, of wider applicability and yield somewhat better results.
Keywords: Computational Indistinguishability, Pseudorandomness, One-Way Functions, Hard-Core Predicates, Fourier Analysis.
comment: written mostly in 1991. See Arcive record Arc-05 for exposition of Yao's XOR Lemma.
contact author: oded@wisdom.weizmann.ac.il
Fetch PostScript file of the full paper.