On Yaos XOR-Lemma

Oded Goldreich, Noam Nisan, and Avi Wigderson

Abstract. A fundamental lemma of Yao states that computational weak-

unpredictability of Boolean predicates is amplified when the results of
several independent instances are XOR together. We survey two known
proofs of Yaos Lemma and present a third alternative proof. The third
proof proceeds by first proving that a function constructed by concatenat-
ing the values of the original function on several independent instances is
much more unpredictable, with respect to specified complexity bounds,
than the original function. This statement turns out to be easier to prove
than the XOR-Lemma. Using a result of Goldreich and Levin (1989) and
some elementary observation, we derive the XOR-Lemma.

Keywords: Yaos XOR Lemma, Direct Product Lemma, One-Way Func-

tions, Hard-Core Predicates, Hard-Core Regions.

An early version of this survey appeared as TR95-050 of ECCC, and was revised
several times (with the latest revision posted in January 1999). Since the first
publication of this survey, Yaos XOR Lemma has been the subject of inten-
sive research. The current revision contains a short review of this research (see
Section 7), but the main text (i.e., Sections 16) is not updated according to
these subsequent discoveries. The current version also include a new appendix
(Appendix B), which discusses a variant of the XOR Lemma, called the Selective
XOR Lemma.

1 Introduction

A fundamental lemma of Yao states that computational weak-unpredictability

of Boolean predicates is amplified when the results of several independent in-
stances are XOR together. Indeed, this is analogously to the information theo-
retic wire-tape channel Theorem (cf., Wyner), but the computational analogue
is significanly more complex.
Loosly speaking, by weak-unpredictability we mean that any efficient algo-
rithm will fail to guess the value of the function with probability beyond a stated
bound, where the probability is taken over all possible inputs (say, with uniform
probability distribution). In particular, the lemma known as Yaos XOR Lemma
asserts that if the predicate f is weakly-unpredictable (within some complexity
bound), then for sufficiently large t (which depends on the bound) the predicate
def
F (x1 , ..., xt ) = ti=1 f (xi ) is almost unpredictable within a related complexity
bound (i.e., algorithms of this complexity cannot do substantially better than
flip a coin for the answer).
2

Yao stated the XOR Lemma in the context of one-way functions, where the
predicate f is the composition of an easy to compute Boolean predicate and the
inverse of the one-way function (i.e., f (x) = b(g 1 (x)), where g is a 1-1 one-
way function and b is an easy to compute predicate). Clearly, this is a special
case of the setting described above. Yet, the XOR Lemma is sometimes used
within the more general setting (under the false assumption that proofs for this
setting have appeared in the literature). Furthermore, in contrary to common
beliefs, the lemma itself has not appeared in Yaos original paper Theory and
Applications of Trapdoor Functions [17] (but rather in oral presentations of his
work).
A proof of Yaos XOR Lemma has first appeared in Levins paper [12]. Levins
proof is for the context of one-way functions and is carried through in a uniform
model of complexity. The presentation of this proof in [12] is very succinct and
does not decouple the basic approach from difficulties arising from the uniform-
complexity model. In Section 3, we show that Levins basic approach suffices
for the general case (mentioned above) provided it is stated in terms of non-
uniform complexity. The proof also extends to a uniform-complexity setting,
provided that some sampling condition (which is satisfied in the context of one-
way functions) holds. We do not know whether the XOR Lemma holds in the
uniform-complexity model in case this sampling condition is not satisfied.
Recently, Impagliazzo has shown that, in the non-uniform model, any weakly-
unpredictable predicate has a hard-core1 on which it is almost unpredictable [7].
Using this result, Impagliazzo has presented an alternative proof for the general
case of the XOR-Lemma (within the non-uniform model). We present this proof
in Section 4.
A third proof for the general case of the XOR-Lemma is presented in Sec-
tion 5. This proof proceeds by first proving that a function constructed by con-
catenating the values of the predicate on several independent instances is much
more unpredictable, with respect to specified complexity bounds, than the orig-
inal predicate. Loosely speaking, it is hard to predict the value of the function
with probability substantially higher than t , where is a bound on the prob-
ability of predicting the predicate and t is the number of instances concate-
nated. Not surprisingly, this statement turns out to be easier to prove than the
XOR-Lemma. Using a result of Goldreich and Levin [5] and some elementary
observation, we derive the XOR-Lemma.
We remark that Levins proof yields a stronger quantitative statement of
the XOR Lemma than the other two proofs. In fact, the quantitative statement
provided by Levins proof is almost optimal. Both Levins proof and our proof
can be transformed to the uniform-complexity provided some natural sampling
condition holds. We do not know how to transform Impagliazzos proof to the
uniform-complexity setting, even under this condition.

1
Here the term hard-core means a subset of the predicates domain. This meaning
is certainly different from the usage of the term hard-core in [5], where it means a
strongly-unpredicatable predicate associated with a one-way function.
 3

A different perspective on the concatenating problem considered above is

presented in Section 6, where we consider the conditional entropy of the func-
tions value given the result of a computation (rather than the probability that
the two agree).

2 Formal Setting

We present a general framework, and view the context of one-way functions

as a specail case. The general framework is presented in term of non-uniform
complexity, but uniformity conditions can be added in.

2.1 The basic setting

The basic framework consists of a Boolean predicate f : {0, 1} {0, 1} and

a non-uniform complexity class such as P/poly. Specifically, we consider all
families of polynomial-size circuits and for each family, {Cn }, we consider the
probability that it correctly computes f , where the probability is taken over
all n-bit inputs with uniform probability distribution. Alternatively, one may
consider the most successful n-bit input circuit among all circuits of a given size.
This way we obtain a bound on unpredictability of f with respect to a specific
complexity class.
In the sequel, it will be more convenient to redefine f as mapping bit string
into {1} and to consider the correlation of a circuit (outputting a value in
def
{1}) with the value of the function (i.e., redefine f (x) = (1)f (x) ).2 Using
this notation allows to replace Prob[C(X) = f (X)] by (1 + E[C(X) f (X)])/2,
by noting that E[C(X) f (X)] = Prob[C(X) = f (X)] Prob[C(X) 6= f (X)].
We also generalize the treatment to arbitrary distributions over the set of
n-bit long inputs (rather than uniform ones) and to probabilistic predicates
(or processes) that on input x return some distribution on {1}; that is, for a
fixed x, we let f (x) be a random variable distributed over {1} (rather than a
fixed value). One motivation for this generalization is that it allows us to treat
as a special case hard predicates of one-way functions, when the functions are
not necessarily 1-1.

Definition 1 (algorithmic correlation): Let P be a randomized process/algorithm

def
that maps bit strings into values in {1} and let X = {Xn } be a probability en-
semble such that, for each n, the random variable Xn is distributed over {0, 1}n.
The correlation of a circuit family C = {Cn } with P over X is defined as c : N R
such that
def
c(n) = E[Cn (Xn ) P (Xn )],
2
This suggestion, of replacing the standard {0, 1} by {1} and using correlations
rather than probabilities, is due to Levin. It is indeed amazing how this simple
change of notation simplifies both the statements and the proofs.
4

where the expectation is taken over the random variable Xn (and the process P ).
We say that a complexity class (i.e., a set of circuit families) has correlation at
most c() with P over X if, for every circuit family C in this class, the correlation
of C with P over X is bounded by c().

The foregoing definition may be used to discuss both uniform and non-uniform
complexity classes. In the next subsection we relate the Definition 1 to the stan-
dard treatment of unpredictability within the context of one-way functions.

2.2 The context of one-way functions

For sake of simplicity, we consider only length-preserving functions (i.e., func-

tions f : {0, 1} {0, 1} satisfying |f (x)| = |x| for all x). A one-way function
f : {0, 1} {0, 1} is a function that is easy to compute but hard to invert.
Namely, there exists a polynomial-time algorithm for computing f , but for any
probabilistic polynomial-time3 algorithm A, the probability that A(f (x)) is a
preimage of f (x) is negligible (i.e., smaller than 1/p(|x|) for any positive poly-
nomial p), where the probability is taken uniformly over all x {0, 1}n and all
possible internal coin tosses of algorithm A.
Let b : {0, 1} {1} be an easy to compute predicate and let : N R. The
predicate b is said to be at most -correlated to f in polynomial-time if for any
probabilistic polynomial-time algorithm G, the expected correlation of G(f (x))
and b(x), is at most (n) (for all but finitely many ns). (Again, the probability
space is uniform over all x {0, 1}n and all possible internal coin tosses of the
algorithm.) Thus, although b is easy to evaluate (i.e., the mapping x 7 b(x) is
polynomial-time computable), it is hard to predict b(x) from f (x), for a random
x.
Let us relate the latter notion to Definition 1. Suppose, first, that f is 1-1.
Then, saying that b is at most -correlated to f in polynomial-time is equiva-
lent to saying that the class of (probabilistic) polynomial-time algorithms has
def
correlation at most () with the predicate P (x) = b(f 1 (x)), over the uniform
distribution. Note that if f is polynomial-time computable and b is at most
(1 (1/poly))-correlated to f in polynomial-time, then f must be one-way (be-
cause otherwise b(x) can be correlated too well by first obtaining f 1 (x) and
then evaluating b),
The treatment can be extended to arbitrary one-way functions, which are
not necessarily 1-1. Let f be such a function and b a predicate that is at most -
correlated to f (by polynomial-time algorithms). Define the probability ensemble
X = {Xn } by letting Xn = f (r), where r is uniformly selected in {0, 1}n,
and define the randomized process P (x) by uniformly selecting r f 1 (x) and
outputting b(r). Now, it follows that the class of (probabilistic) polynomial-time
algorithms has correlation at most () with the predicate P over X.
3
Here we adopt the standard definition of one-way function; however, our treatment
applies also to the general definition where inverting is infeasible with respect to a
specified time bound and success probability.
 5

2.3 Getting random examples

An important issue regarding the general setting, is whether it is possible to
obtain random examples of the distribution (Xn , P (Xn )). Indeed, random exam-
ples are needed in all known proofs of the XOR Lemma (i.e., they are used in
the algorithms deriving a contradiction to the difficulty of correlating the basic
predicate).4 Other than this aspect (i.e., the use of random examples), two of the
three proofs can be adapted to the uniform-complexity setting (see Section 2.5).
Note that in the context of one-way functions such random examples can be
generated by a probabilistic polynomial-time algorithm. Specifically, although
the corresponding P is assumed not to be polynomial-time computable, it is easy
to generate randomly pairs (x, P (x)) for x Xn . (This is done, by uniformly
selecting r {0, 1}n , and outputting the pair (f (r), b(r)) = (f (r), P (f (r))).)
Thus, we can prove the XOR Lemma in the (uniform-complexity) context of
one-way functions.
We also note that the effect of random examples can be easily simulated by
non-uniform polynomial-size circuits (i.e., random examples can be hard-wired
into the circuit). Thus, we can prove the XOR Lemma in the general non-uniform
complexity setting.

2.4 Three (non-uniform) forms of the XOR Lemma

Following the description in the introduction (and Yaos expositions), the basic
form of the XOR Lemma states that the tractable algorithmic correlation of the
def Qt
XOR-predicate P (t) (x1 , ..., xt ) = i=1 P (xi ) decays exponentially with t (upto
a negligible fraction). Namely:
Lemma 1 (XOR Lemma Yaos version): Let P and X = {Xn } be as in Defi-
nition 1. For every function t : N N, define the predicate
t(n)
def
Y
P (t) (x1 , ..., xt(n) ) = P (xi ) ,
i=1

def (t)
where x1 , ..., xt(n) {0, 1}n, and let X(t) = {Xn } be a probability ensemble
(t)
such that Xn consists of t(n) independent copies of Xn .
(hypothesis) Let s : N N be a size function, and : N [1, +1] be a function
1
that is bounded-away-from-1 (i.e., |(n)| < 1 p(n) , for some polynomial
p and all sufficiently large ns). Suppose that is an upper bound on the
correlation of families of s()-size circuits with P over X.
(conclusion) Then, there exists a bounded-away-from-1 function : N [1, +1]
and a polynomial p such that, for every function t : N N and every function
: N [0, 1], the function
def
(t) (n) = p(n) (n)t(n) + (n)
4
This assertion refers to what was known at the time this survey was written. As
noted in Section 7, the situation regarding this issue has changed recently.
6

is an upper bound on the correlation of families of s ()-size circuits with P (t)

over X(t) , where
 
def (n)
s (t(n) n) = poly s(n) poly(n t(n)).
n
All three proofs presented below establish Lemma 1. The later two proofs do
so for various values of and p; that is, in Impagliazzos proof (see Section 4)
(n) = 1+(n) + o(1 (n)) and p(n) = 2, whereas in our proof (see Section 5)
q2
3 1+(n)
(n) = 2 and p(n) = o(n). Levins proof (see Section 3) does even better;
it establishes the following:
Lemma 2 (XOR Lemma Levins version): Yaos version holds with =
and p = 1.
Lemma 2 still contains some slackness; specifically, the closest one wants to get
to the obvious bound of (t) (n) = (n)t(n) , the more one losses in terms of the
complexity bounds (i.e., bounds on circuit size).5 In particular, if one wishes to
s(n)
have s (t(n) n) = poly(n) , then one can only get a result for (n) = 1/poly(n)
(i.e., get (t) (n) = (n)t(n) + 1/p(n), for any polynomial p). We do not know how
to remove this slackness. We even do not know if it can be reduced a little as
follows.
Lemma 3 (XOR Lemma dream version a conjecture): For some fixed neg-
def def 2
ligible function (e.g., (n) = 2n or even (n) = 2(log2 n) ), Yaos version
s(n)
holds with (t) (n) = (n)t(n) + (n), and s (t(n) n) = poly(n) .

Steven Rudich has observed that the Dream Version does not hold in a relativized
world. Specifically, his argument proceeds as follows. Fix as in the Dream
Version and set t such that (t) < 2(n). Consider an oracle that for every
(x1 , ..., xt(n) ) ({0, 1}n )t(n) and for a 2(n) fraction of the rs in {0, 1}n, answers
the query (x1 , ..., xt(n) , r) with (P (x1 ), ..., P (xt )), otherwise the oracle answers
with a special symbol. These rs may be selected at random (thus constructing
a random oracle). The hypothesis of the lemma may hold relative to this oracle,
but the conclusion cannot possibly hold. Put differently, one can argue that
there is no (polynomial-time) black-box reduction of the task of correlating P
(by at least ) to the task of correlating P (t) (by at least ). The reason being
that the polynomial-time machine (effecting this reduction) cannot distinguish a
black-box of negligible correlation (i.e., correlation 2) from a black-box of zero
correlation.

2.5 Uniform forms of the XOR Lemma

So far, we have stated three forms of the XOR Lemma in terms of non-uniform
complexity. Analogous statements in terms of uniform complexity can be made
5
I.e., (t) (n) = (n)t(n) + (n) is achieved for s (t(n) n) = poly((n)/n) s(n).
 7

as well. These statements relate to the time required to construct the circuits
in the hypothesis and those in the conclusion. For example, one may refer to
circuit families, {Cn }, for which, given n, the circuit Cn can be constructed in
poly(|Cn |)-time. In addition, all functions referred to in the statement of the
lemma (i.e., s, t : N N, : N [1, +1] and : N [1, +1]) need to be
computable within corresponding time bounds. Such analogues of the two first
versions can be proven, provided that one can construct random examples of the
distribution (Xn , P (Xn )) within the stated (uniform) complexity bounds (and
in particular in polynomial-time). See Section 2.3 as well as comments in the
subsequent sections.

3 Levins Proof

The key ingredient in Levins proof is the following lemma, which provides an
accurate account of the decrease of the computational correlation in the case
that two predicates are xor-ed together. It should be stressed that the statement
of the lemma is intentionally asymmetric with respect to the two predicates.

Lemma 4 (Isolation Lemma): Let P1 and P2 be two predicates, l : N N be

def
a length function, and P (x) = P1 (y) P2 (z) where x = yz and |y| = l(|x|).
Let X = {Xn } be a probability ensemble such that the first l(n) bits of Xn are
statistically independent of the rest, and let Y = {Yl(n) } (resp., Z = {Znl(n) })
denote the projection of X on the first l() bits (resp., last n l(n) bits).

(hypothesis) Suppose that 1 () is an upper bound on the correlation of families

of s1 ()-size circuits with P1 over Y, and that 2 () is an upper bound on the
correlation of families of s2 ()-size circuits with P2 over Z.
(conclusion) Then, for every function : N R, the function
def
(n) = 1 (l(n)) 2 (n l(n)) + (n)

is an upper bound on the correlation of families of s()-size circuits with P

over X, where
 
def s1 (l(n))
s(n) = min , s2 (n l(n)) n
poly(n/(n))

The lemma is asymmetric with respect to the dependency of s() on the si s.

The fact that s() maybe almost equal to s2 () plays a central role in deriving
the XOR Lemma from the Isolation Lemma.

3.1 Proof of the Isolation Lemma

Assume, towards the contradiction, that a circuit family C (of size s()) has
correlation greater than () with P over X. Thus, denoting by Yl (resp., Zm )
8

def def
the projection of Xn on the first l = l(n) bits (resp., last m = n l(n) bits),
we get

(n) < E[Cn (Xn ) P (Xn )]

= E[Cn (Yl , Zm ) P1 (Yl ) P2 (Zm )]
= E[P1 (Yl ) E[Cn (Yl , Zm ) P2 (Zm )]]

where, in the last expression, the outer expectation is over Yl and the inner one
is over Zm . For every fixed y {0, 1}l, let
def
T (y) = E[Cn (y, Zm ) P2 (Zm )]. (1)

Then, by the foregoing,

E[T (Yl ) P1 (Yl )] > (n). (2)

We shall see that Eq. (2) either contradicts the hypothesis concerning P2 (see
Claim 4.1) or contradicts the hypothesis concerning P1 (by a slightly more in-
volved argument).
Claim 4.1: For all but finitely many ns and every y {0, 1}l

|T (y)| 2 (m).
def
Proof: Otherwise, fixing a y contradicting the claim, we get a circuit Cm (z) =
Cn (y, z) of size s(n) + l < s2 (m), having greater correlation with P2 than that
allowed by the lemmas hypothesis.
By Claim 4.1, the value T (y)/2 (m) lies in the interval [1, +1]; while, on the
other hand (by Eq. (2)), it (i.e., T ()/2 (m)) has good correlation with P1 . In
the rest of the argument we transform the function T into a circuit which
contradicts the hypothesis concerning P1 . Suppose for a moment, that one could
compute T (y), on input y. Then, one would get an algorithm with output in
[1, +1] that has correlation at least (n)/2 (m) > 1 (l) with P1 over Yl , which
is almost in contradiction to the hypothesis of the lemma.6 The same holds if
one can approximate T (y) well enough using circuits of size s1 (l). Indeed, the
lemma follows by observing that such an approximation is possible. Namely:
Claim 4.2: For every n, l = l(n), m = n l, q = poly(n/(n)) and y {0, 1}l, let
q
def 1
T(y) =
X
Cn (y, zi ) i
q i=1

where (z1 , 1 ), ..., (zq , q ) is a sequence of q independent samples from the dis-
tribution (Zm , P2 (Zm )). Then,

Prob[|T (y) T(y)| > (n)] < 2l(n)

6
See discussion below; the issue is that the output is in the interval [1, +1] rather
than being a binary value in {1}.
 9

Proof: Immediate by the definition of T (y) and application of Chernoff bound.

Claim 4.2 suggests an approximation algorithm (for the function T ), where we

assume that the algorithm is given as auxiliary input a sequence of samples from
the distribution (Zm , P2 (Zm )). (The algorithm merely computes the average of
Cn (y, zi ) i over the sample sequence (z1 , 1 ), ..., (zq , q ).)
If such a sample sequence can be generated efficiently, by a uniform algorithm
(as in the context of one-way functions), then we are done. Otherwise, we use
non-uniformity to obtain a fixed sequence that is good for all possible ys. (Such a
sequence does exist since with positive probability, a randomly selected sequence,
from the above distribution, is good for all 2l(n) possible ys.) Thus, there exists
a circuit of size poly(n/(n)) s(n) that, on input y {0, 1}l(n), outputs a value
(T (y) (n))/2 (m).
We note that this output is at least (n)2 (m)
(n)
2 (m)
= 1 (l) correlated with
P1 , which almost contradicts the hypothesis of the lemma. The only problem is
that the resulting circuit has output in the interval [1, +1] instead of a binary
output in {1}. This problem is easily corrected by modifying the circuit so
that on output r [1, +1] it outputs +1 with probability (1 + r)/2 and 1
otherwise. Noting that this modification preserves the correlation of the circuit,
we derive a contradiction to the hypothesis concerning P1 .

3.2 Proof of Lemma 2

The stronger version of the XOR Lemma (i.e., Lemma 2) follows by a (care-
ful) successive application of the Isolation Lemma. Loosely speaking, we write
P (t) (x1 , x2 , ..., xt(n) ) = P (x1 )P (t1) (x2 , ..., xt(n) ), assume that P (t1) is hard to
correlate as claimed, and apply the Isolation Lemma to P P (t1) . This way, the
lower bound on the size of circuits correlating P (t) is related to the lower bound
assumed for circuits correlating the original P , since the lower bound derived for
P (t1) is larger and is almost preserved by the Isolation Lemma (losing only an
additive term!).

3.3 Remarks concerning the uniform complexity setting

A uniform-complexity analogue of Lemma 2 can be proven provided that one can
construct random examples of the distribution (Xn , P (Xn )) within the stated
(uniform) complexity bounds. To this end, one should state and prove a uniform-
complexity version of the Isolation Lemma, which also assumes that example
from both distributions (i.e., (Yl , P1 (Yl )) and (Zm , P2 (Zm )))7 can be generated
within the relevant time complexity; certainly, sampleability in probabilistic
polynomial-time suffices. Furthermore, in order to derive the XOR Lemma it
is important to prove a strong statement regarding the relationship between the
time required to construct the circuits referred to in the lemma. Namely:
7
Actually, it suffices to be able to sample the distributions Yl and (Zm , P2 (Zm )).
10

Lemma 5 (Isolation Lemma uniform complexity version): Let P1 , P2 , l, P, X, Y

and Z be as in Lemma 4.

(hypothesis) Suppose that 1 () (resp., 2 ) is an upper bound on the correlation of

t1 ()-time-constructible families of s1 ()-size (resp., t2 ()-time-constructible
families of s2 ()-size) circuits with P1 over Y (resp., P2 over Z). Further-
more, suppose that one can generate in polynomial-time a random sample
from the distribution (Yl , Zm , P2 (Zm )).
(conclusion) Then, for every function : N R, the function
def
(n) = 1 (l(n)) 2 (n l(n)) + (n)

is an upper bound on the correlation of t()-time-constructible families of

s()-size circuits with P over X, where
 
def s1 (l(n))
s(n) = min , s2 (n l(n)) n
poly(n/(n))
def
t(n) = min {t1 (l(n)) , t2 (n l(n))} poly(n/(n)) s(n).

The uniform-complexity version of the Isolation Lemma is proven by adapting

the proof of Lemma 4 as follows. First, a weaker version of Claim 4.1 is stated,
asserting that (for all but finitely many ns) it holds that

Prob[|T (Yl )| > 2 (m) + (n)] < (n),

def
where (n) = (n)/3. The new claim is valid, since otherwise, one can find in
poly(n/(n))-time a y violating it; to this end we need to sample Yl and, for
each sample y, approximate the value of T (y) (by using poly(n/(n)) samples of
(Zm , P2 (Zm ))). Once a good y is found, we incorporate it in the construction of
Cn , obtaining a circuit that contradicts the hypothesis concerning P2 . (We stress
that we have presented an efficient algorithm for constructing a circuit for P2 ,
given an algorithm that constructs the circuit Cn . Furthermore, the running time
of our algorithm is the sum of the time required to construct Cn and the time
required for sampling (Zm , P2 (Zm )) sufficiently many times and for evaluating
Cn on sufficiently many instances.)
Clearly, Claim 4.2 remains unchanged (except for the replacing (n) by ).
Using the hypothesis that samples from (Zm , P2 (Zm )) can be efficiently gener-
ated, we can construct a circuit for correlating P1 within time t(n)+poly(n/(n))
(n + s(n)). This circuit is merely an approximater of the function T , which op-
erates by averaging (as in Claim 4.2); this circuit is constructed by first con-
structing Cn , generating poly(n/(n)) samples of (Zm , P2 (Zm )) and incorporat-
ing them in corresponding copies of Cn thus justifying the above time and size
bounds. However, unlike in the non-uniform case, we are not guaranteed that
|T (y)| is bounded above (by 2 (m) + (n)) for all ys. Yet, if we modify our
circuit to do nothing whenever its estimate violates the bound, we loss at most
(n) of the correlation and we can proceed as in the non-uniform case.
 11

Proving a uniform complexity version of Lemma 2: As in the non-uniform

case, the (strong form of the) XOR Lemma follows by a (careful) successive
application of the Isolation Lemma. Again, we write P ( ) (x1 , x2 , ..., x (n) ) =
P (x1 )P ( 1) (x1 , ..., x (n)1 ), assume that P ( 1) is hard to correlate as claimed,
and apply the Isolation Lemma to P P ( 1) . This way, the lower bounds on
circuits correlating P ( ) is related to the lower bound assumed for circuits corre-
lating the original P and is almost the bound derived for P ( 1) (losing only an
additive terms!). This almost concludes the proof, except that we have implicitly
assumed that we know the value of for which the XOR Lemma first fails; this
value is needed in order to construct the circuit violating the hypothesis for the
original P . In the non-uniform case this value of can be incorporated into the
circuit, but in the uniform-complexity case we need to find it. This is not a big
problem as they are only polynomially many possible values and we can test
each of them within the allowed time complexity.

4 Impagliazzos Proof

The key ingredient in Impagliazzos proof is the notion of a hard-core region of

a weakly-unpredictable predicate and a lemma that asserts that every weakly-
unpredictable predicate has a hard-core region of substantial size.

Definition 2 (hard-core region of a predicate): Let f : {0, 1} {0, 1} be a

Boolean predicate, s : N N be a size function, and : N [0, 1] be a function.

We say that a sequence of sets, S = {Sn {0, 1}n}, is a hard-core (region)

of f with respect to s()-size circuits families and advantage () if for every
n and every circuit Cn of size at most s(n), it holds that

1
Prob[Cn (Xn ) = f (Xn )] + (n)
2
where Xn is a random variable uniformly distributed on Sn .
We say that f has a hard-core (region) of density () with respect to s()-
size circuits families and advantage () if there exists a sequence of sets
S = {Sn {0, 1}n} such that S is a hard-core of f with respect to the above
and |Sn | (n) 2n .

We stress that the usage of the term hard-core in the above definition (and in
the rest of this section) is different from the usage of this term in [5]. Observe
that every strongly-unpredictable predicate has a hard-core of density 1 (i.e.,
the entire domain itself). Impagliazzo proves that also weakly-unpredicatabe
predicates have hard-core sets that have density related to the amount of unpre-
dictability. Namely:

Lemma 6 (existence of hard-core regions for unpredictable predicates): Let f :

{0, 1} {0, 1} be a Boolean predicate, s : N N be a size function, and : N
12

[0, 1] be a noticeable function (i.e., (n) > 1/poly(n)), such that for every n and
every circuit Cn of size at most s(n) it holds that

Prob[Cn (Un ) = f (Un )] 1 (n),

where Un is a random variable uniformly distributed on {0, 1}n. Then, for every
function : N [0, 1], the function f has a hard-core of density () with respect
def
to s ()-size circuits families and advantage (), where (n) = (1 o(1)) (n)
def
and s (n) = s(n)/poly(n/(n)).

The proof of Lemma 6 is given in Appendix A. Using Lemma 6, we derive a

proof of the XOR-Lemma, for the special case of uniform distribution.
Suppose that () is a bound on the correlation of s()-circuits with f over
the uniform distribution. Then, it follows that such circuits cannot guess the
def
value of f better than with probability p(n) = 1+(n) 2 and the existence of
a hard-core S = {Sn } (w.r.t. s (n)-circuits and (n)-advantage) with density
def
(n) = (1 o(1)) (1 p(n)) follows. Clearly,

1 (n) 1
(n) = (1 o(1)) > (1 (n)).
2 3

Now, suppose that in contradiction to the XOR Lemma, the predicate F (t) de-
def
fined as F (t) (x1 , ..., xt ) = i f (xi ) can be correlated by small circuits with
def
correlation greater than c (n) = 2 ( 2+(n)
3 )t + (n). In other words, such cir-
cuits can guess F with success probability at least 21 + 12 c (n). However, the
(t)

probability that none of the t arguments to F (t) falls in the hard-core is at most
(1 (n))t . Thus, conditioned on the event that at least one argument falls in
the hard-core S, the circuit guess F (t) correctly with probability at least

1 1 1 (n)
+ c (n) (1 (n))t > +
2 2 2 2 .
Note, however, that this does not seem to yield an immediate contradition to
the definition of a hard-core of f , yet we shall see that such a contradiction can
be derived.
For every non-empty I {1, ..., t}, we consider the event, denoted EI , that
represents the case that the arguments to F (t) that fall in the hard-core of f are
exactly those with index in I. We have just shown that, conditioned on the union
of these events, the circuit guesses the predicate F (t) correctly with probability
at least 21 + (n)
2 . Thus, there exists an (non-empty) I such that, conditioned
on EI , the circuit guesses F (t) correctly with probability at least 21 + (n)
2 . Let
i I be arbitrary. By another averaging argument, we fix all inputs to the circuit
except the ith input and obtain a circuit that guesses f correctly with probability
at least 21 + (n)
2 . (For these fixed xj s, j 6= i, the circuit incorporates also the
value of j6=i f (xj ).) This contradicts the hypothesis that S is a hard-core.
 13

Generalization. We have just established the validity of the Lemma 1 for the case
of the uniform probability ensemble and parameters p(n) = 2 and (n) = 2+(n)
3 .
The bound for can be improved to (n) = 1+(n)
2 + o(1 (n)). The argument
extends to arbitrary probability ensembles. To this end one needs to properly
generalize Definition 2 and prove a generalization of Lemma 6; for details the
interested reader is referred to Appendix A.

5 Going through the direct product problem

The third proof of the XOR Lemma proceeds in two steps. First it is shown
that the success probability of feasible algorithms that try to predict the values
of a predicate on several unrelated arguments decreases exponentially with the
number of arguments. This statement is a generalization of another theorem
due to Yao [17], hereafter called the Concatenation Lemma. Invoking a result of
Goldreich and Levin [5], the XOR-Lemma follows.

5.1 The Concatenation Lemma

(This lemma is currently called the Direct Product Theorem.)

Lemma 7 (concatenation lemma): Let P , X = {Xn }, s : N N, and : N

[1, +1] be as in Lemma 1. For every function t : N N, define the function
def
F (t) (x1 , ..., xt(n) ) = (P (x1 ), ..., P (xt(n) )), where x1 , ..., xt(n) {0, 1}n , and the
(t) (t)
probability ensemble X(t) = {Xn }, where Xn consists of t(n) independent
copies of Xn .
(hypothesis) Suppose that is an upper bound on the correlation of families of
s()-size circuits with P over X. Namely, suppose that for every n and for
every s(n)-size circuit C, it holds that

def 1 + (n)
Prob[C(Xn ) = P (Xn )] p(n) =
2 .

(conclusion) Then, for every function : N [0, +1], for every n and for every
poly( (n)
n ) s(n)-size circuit C , it holds that

Prob[C (Xn(t) ) = F (t) (Xn(t) )] p(n)t(n) + (n).

Remark. Nisan et. al. [14] have used the XOR-Lemma in order to derive the
Concatenation Lemma. Our feeling is that the Concatenation Lemma is more
basic than the XOR Lemma, and thus that their strategy is not very natural.8
In fact, this feeling was our motivation for trying to find a direct proof for
8
This assertion is supported by a recent work of Viola and Wigderson, which pro-
vides a very simple proof that, in the general setting, the XOR Lemma implies the
Concatenation Lemma [16, Prop. 1.4].
14

the Concatenation Lemma. Extrapolating from the situation regarding the two
original lemmata of Yao (i.e., the XOR Lemma and the Concatenation Lemma
w.r.t. one-way functions),9 we believed that such a proof (for the Concatenation
Lemma) should be easy to find. Indeed, we consider the following proof of Con-
catenation Lemma much simpler than the proofs of the XOR Lemma (given in
previous sections).

A tight two-argument version. Lemma 7 is derived from the following Lemma 8

(which is a tight two-argument version of Lemma 7) analogously to the way that
Lemma 2 was derived from Lemma 4; that is, we write F (t) (x1 , x2 , ..., xt(n) ) =
(P (x1 ), F (t1) (x2 , ..., xt(n) )), assume that F (t1) is hard to guess as claimed, and
apply the Concatenation Lemma to (P, F (t1) ). This way, the lower bound on
circuits guessing F (t) is related to the lower bound assumed for circuits guessing
the original P and is almost the bound derived for F (t1) (losing only an additive
term!). It is thus left to prove the following two-argument version.

Lemma 8 (two argument version of concatenation lemma): Let F1 and F2 be

def
two functions, l : N N be a length function, and F (x) = (F1 (y), F2 (z)) where
x = yz and |y| = l(|x|). Let X = {Xn }, Y = {Yl(n) } and Z = {Znl(n) } be
probability ensembles as in Lemma 4 (i.e., Xn = (Yl(n) , Znl(n) )).
(hypothesis) Suppose that p1 () is an upper bound on the probability that families
of s1 ()-size circuits guess F1 over Y. Namely, for every such circuit family
C = {Cl } it holds that

Prob[Cl (Yl ) = F1 (Yl )] p1 (l).

Likewise, suppose that p2 () is an upper bound on the probability that families

of s2 ()-size circuits guess F2 over Z.
def
(conclusion) Then, for every function : N R, the function p(n) = p1 (l(n))
p2 (n l(n)) + (n) is an upper bound on the probability that families of
s()-size circuits guess F over X, where
 
def s1 (l(n))
s(n) = min , s2 (n l(n)) n
poly(n/(n)) .

Proof: Let C = {Cn } be a family of s()-size circuits. Fix an arbitrary n, and

write C = Cn , = (n), l = l(n), m = n l(n), Y = Yl and Z = Zm . Abusing
notation, we let C1 (x, y) denote the first component of C(x, y) (i.e., the guess
9
Yaos original XOR Lemma (resp., Concatenation Lemma) refers to the setting of
one-way functions. In this setting, the basic predicate P is a composition of an easy
def
to compute predicate b and the inverse of a 1-1 one-way function f ; i.e., P (x) =
b(f 1 (x)). For years, the first author has considered the proof of the XOR Lemma
(even for this setting) too complicated to be presented in class; whereas, a proof of
the Concatenation Lemma (for this setting) has appeared in his classnotes [1] (see
also [2]).
 15

for F1 (x)) and likewise C2 (x, y) is Cs guess for F2 (y). It is instructive to write
the success probability of C as follows:

Prob[C(Y, Z) = F (Y, Z)] = Prob[C2 (Y, Z) = F2 (Z)]

Prob[C1 (Y, Z) = F1 (Y ) | C2 (Y, Z) = F2 (Z)]

The basic idea is that using the hypothesis regarding F2 allows to bound the
first factor by p2 (m), whereas the hypothesis regarding F1 allows to bound the
second factor by approximately p1 (l). The basic idea for the latter step is that a
sufficiently large sample of (Z, F2 (Z)), which may be hard-wired into the circuit,
allows to use the conditional probability space (in such a circuit), provided the
condition holds with noticeable probability. The last caveat motivates a separate
treatment for ys with noticeable Prob[C2 (y, Z) = F2 (Z)] and for the rest.
We call y good if Prob[C2 (y, Z) = F2 (Z)] /2 and bad otherwise. Let G be
the set of good ys. Then, using Prob[C(Y, Z) = F (Y, Z)] < /2 for every bad y,
we upper bound the success probability of C as follows

Prob[C(Y, Z) = F (Y, Z)] = Prob[C(Y, Z) = F (Y, Z) & Y G]

+ Prob[C(Y, Z) = F (Y, Z) & Y 6 G]

< Prob[C(Y, Z) = F (Y, Z) & Y G] +
2.
Thus, using p(n) = p1 (l) p2 (m) + , it remains to prove that

Prob[C(Y, Z) = F (Y, Z) & Y G] p1 (l) p2 (m) + /2. (3)

We proceed according to the foregoing outline. We first show that Prob[C2 (Y, Z) = F2 (Z)]
cannot be too large, as otherwise the hypothesis concerning F2 is violate. Actu-
ally, we prove the following
Claim 8.1: For every y, it holds that

Prob[C2 (y, Z) = F2 (Z)] p2 (m).

Proof: Otherwise, using any y {0, 1}l such that Prob[C2 (y, Z) = F2 (Z)] >
def
p2 (m), we get a circuit C (z) = C2 (y, z) that contradicts the lemmas hypothesis
concerning F2 .

Next, we use Claim 8.1 in order to relate the success probability of C to the
success probability of small circuits for F1 .
Claim 8.2: There exists a circuit C of size s1 (l) such that

Prob[C(Y, Z) = F (Y, Z) & Y G]

Prob[C (Y ) = F1 (Y )]
p2 (m) 2.

Proof: The circuit C is constructed as suggested in the foregoing outline. Specifi-

cally, we take a poly(n/)-large sample, denoted S, from the distribution (Z, F2 (Z))
16

def
and let C (y) = C1 (y, z), where (z, ) is a uniformly selected among the ele-
ments of S for which C2 (y, z) = holds. Details follow.
def
Let S be a sequence of t = poly(n/) pairs, generated by taking t inde-
pendent samples from the distribution (Z, F2 (Z)). We stress that we do not
assume here that such a sample can be produced by an efficient (uniform) al-
gorithm (but, jumping ahead, we remark that such a sequence can be fixed
non-uniformly). For each y G {0, 1}l, we denote by Sy the set of pairs
(z, ) S for which C2 (y, z) = . Note that Sy is a random sample for the resid-
ual probability space defined by (Z, F2 (Z)) conditioned on C2 (y, Z) = F2 (Z).
Also, with overwhelmingly high probability, |Sy | = (l/2 ) (since y G implies
Prob[C2 (y, Z) = F2 (Z)] /2). Thus, with overwhelming probability (i.e., prob-
ability greater than 1 2l ), taken over the choices of S, the sample Sy provides
a good approximation to the conditional probability space, and in particular
|{(z, ) Sy : C1 (y, z) = F1 (y)}|
Prob[C1 (y, Z) = F1 (y) | C2 (y, Z) = F2 (Z)]
|Sy | 2
(4)
Thus, with positive probability, Eq. (4) holds for all y G {0, 1}l. The circuit
C guessing F1 is now defined as follows. A set S = {zi , i } satisfying Eq. (4) for
all good ys is hard-wired into the circuit C . (In particular, Sy is not empty
for any good y.) On input y, the circuit C first determines the set Sy , by running
C for t times and checking, for each i = 1, ..., t, whether C2 (y, zi ) = i . In case
Sy is empty, the circuit returns an arbitrary value. Otherwise, the circuit selects
uniformly a pair (z, ) Sy and outputs C1 (y, z). (This latter random choice
can be eliminated by a standard averaging argument.) Using the definition of C
and Eq. (4), we get

Prob[C (Y ) = F1 (Y )]
X
Prob[Y = y] Prob[C (y) = F1 (y)]
yG
X |{(z, ) Sy : C1 (y, z) = F1 (y)}|
= Prob[Y = y]
|Sy |
yG
X  
Prob[Y = y] Prob[C1 (y, Z) = F1 (y) | C2 (y, Z) = F2 (Z)]
2
yG

X Prob[C(y, Z) = F (y, Z)]
Prob[Y = y]
Prob[C2 (y, Z) = F2 (Z)] 2.
yG

Next, using Claim 8.1, we get

X Prob[C(y, Z) = F (y, Z)]
Prob[C (Y ) = F1 (Y )] Prob[Y = y]
p2 (m) 2
yG

and the claim follows.

 17

Now, by the lemmas hypothesis concerning F1 , we have Prob[C (Y ) = F1 (Y )]

p1 (l), and so using Claim 8.2 we get
Prob[Y G & C(Y, Z) = F (Y, Z)] (p1 (l) + /2) p2 (m)
p1 (l) p2 (m) + /2.
This proves Eq. (3) and the lemma follows.

5.2 Deriving the XOR Lemma from the Concatenation Lemma

Using the techniques of Goldreich and Levin [5], we obtain the following result.
Lemma 9 (hard-core predicate of unpredictable functions): Let F : {0, 1}
{0, 1}, p : N [0, 1], and s : N N, and let X = {Xn } be as in Definition 1.
For , {0, 1}, we denote by IP2 (, ) the inner-product mod 2 of and ,
viewed as binary vectors of length .
(hypothesis) Suppose that, for every n and for every s(n)-size circuit C, it holds
that
Prob[C(Xn ) = F (Xn )] p(n).
(conclusion) Then, for some constant c > 0, for every n and for every poly( p(n)
n )
s(n)-size circuit C , it holds that
1 p
Prob[C (Xn , U ) = IP2 (F (Xn ), U )] + c 3 n2 p(n),
2
def
where U denotes the uniform distribution
p over {0, 1} , with = |F (Xn )|.
(That is, C has correlation at most 2c 3 n2 p(n) with IP2 over (F (Xn ), U ).)
def p
Proof Sketch: Let q(n) = c 3 n2 p(n). Suppose that C contradicts the con-
clusion of the lemma. Then, there exists a set S such that Prob[Xn S] q(n)
and for every x S the probability that C (x, U ) = IP2 (F (x), U ) is at least
1 q(n)
2 + 2 , where the probability is taken over U (while x is fixed). Employing
the techniques of [5]10 , we obtain a randomized circuit C (of size at most a
poly(n/p(n)) factor larger than C ) such that, for every x S, it holds that
Prob[C(Xn ) = F (Xn )] c (q(n)/n)2 (where the constant c > 0 is determined
in the proof of [5] according to Chebishevs Inequality).11 Thus, C satisfies
Prob[C(Xn ) = F (Xn )] Prob[C(Xn ) = F (Xn ) Xn S]
= Prob[Xn S] Prob[C(Xn ) = F (Xn )|Xn S]
 
2
q(n) c (q(n)/n) = p(n)

in contradiction to the hypothesis. The lemma follows.

10
See alternative expositions in either [4, Sec. 7.1.3] or [3, Sec. 2.5.2].
11
The algorithm in [5] will actually retrieve all values {0, 1} for which the corre-
lation of C (x, U ) and IP2 (, U ) is at least q(n). With overwhelming probability it
outputs a list of O((n/q(n))2 ) strings containing all the values just mentioned and
thus uniformly selecting one of the values in the list yields F (x) with probability at
least 1/O((n/q(n))2 ).
18

Conclusion. Combining the Concatenation Lemma (Lemma 7) with Lemma 9

we establish the validity of Lemma 1 for the third time;
q this time with respect
to the parameters p(n) = cn2/3 = o(n) and (n) = 3 1+(n) 2 . Details follow.
Starting with a predicate for which is a correlation bound and using
Lemma 7, we get a function that is hard to guess with probability substantially
higher than ( 1+(n)
2 )t(n) . Applying Lemma 9 establishes that given (x1 , ..., xt(n) )
and a uniformly chosen subset S {1, 2, ..., t(n)} it is hard to correlate iS P (xi )
better than with correlation
s !t(n)
 t(n) r
3
2
1 + (n) 3 1 + (n)
O n = o(n)
2 2
.

This is almost what we need, but not quite (what we need is a statement con-
cerning S = {1, ..., t(n)}). The gap is easily bridged by some standard padding
trick. For example, by using a sequence of fixed pairs (zi , i ), such that i =
t(n)
P (zi ), we reduce the computation of iS P (xi ) to the computation of i=1 P (yi )
by setting yi = xi if i S and yi = zi otherwise. (See Appendix B for more
details.) Thus, Lemma 1 follows (with the stated parameters).

5.3 Remarks concerning the uniform complexity setting

A uniform-complexity analogue of the foregoing proof can be carried out pro-
vided that one can construct random examples of the distribution (Xn , P (Xn ))
within the stated (uniform) complexity bounds (and in particular in polynomial-
time). Actually, this condition is required only for the proof of the Concatenation
Lemma. Thus we confine ourselves to presenting a uniform-complexity version
of the Concatenation Lemma.
Lemma 10 (Concatenation Lemma uniform complexity version): Let P, X, s, , t
and F (t) be as in Lemma 7.
(hypothesis) Suppose that () is an upper bound on the correlation of T ()-
time-constructible families of s()-size circuits with P over X. Furthermore,
suppose that one can generate in polynomial-time a random sample from the
distribution (Xn , P (Xn )).
def
(conclusion) Then, for every function : N [0, +1], the function q(n) =
t(n)
p(n) +(n) is an upper bound on the correlation of T ()-time-constructible
families of s ()-size circuits with F over X(t) , where T (t(n)n) = poly((n)/n)
T (n) and s (t(n) n) = poly((n)/n) s(n).
The uniform-complexity version of the Concatenation Lemma is proven by adapt-
ing the proof of Lemma 7 as follows. Firstly, we observe that it suffices to prove
an appropriate (uniform-complexity) version of Lemma 8. This is done by first
proving a weaker version of Claim 8.1 that asserts that for all but at most an
(n)/8 measure of the ys (under Y ), it holds that
Prob[C2 (y, Z) = F2 (Z)] p2 (m) + (n)/8.
 19

This holds because otherwise one may sample Y with the aim of finding a y such
that Prob[C2 (y, Z) = F2 (Z)] > p2 (m) holds, and then use this y to construct
(uniformly!) a circuit that contradicts the hypothesis concerning F2 . Next, we
prove a weaker version of Claim 8.2 by observing that, for a uniformly selected
pair sequence S, with overwhelmingly high probability (and not only with pos-
itive probability), Eq. (4) holds for all good y {0, 1}l. Thus, if we generate
S by taking random samples from the distribution (Zm , F2 (Zm )), then with
overwhelmingly high probability we end-up with a circuit as required by the
modified claim. (The modified claim has p2 (m) + /8 in the denominator (rather
than p2 (m)) as well as an extra additive term of /8.) Using the hypothesis
concerning F1 , we are done as in the non-uniform case.

6 A Different Perspective: the Entropy Angle

The XOR Lemma and the Concatenation Lemma are special cases of the so-
called direct sum conjecture asserting that computational difficulty increases
when many independent instances of the problem are to be solved. In both cases
the direct sum conjecture is postulated by considering insufficient resources
and bounding the probability that these tasks can be performed within these
resources, as a function of the number of instances. In this section we suggest
an analogous analysis based on entropy rather than probability. Specifically, we
consider the amount of information remaining in the task (e.g., of computing
f (x)) when given the result of a computation (e.g., C(x)). This analysis turns
out to be much easier.
Proposition 11 Let f be a predicate, X be a random variable and C be a class
of circuits so that for every circuit C C
H(f (X)|C(X)) ,
where H denotes the (conditional) binary entropy function. Furthermore, suppose
that, for every circuit C C, fixing any of the inputs of C yields a circuit also
in C. Then, for every circuit C C, it holds that
H(f (X (1) ), ..., f (X (t) )|C(X (1) , ..., X (t) )) t ,
where the X (i) s are independently distributed copies of X.
We stress that the class C in Proposition 11 may contain circuits with several
Boolean outputs. Furthermore, for a meaningful conclusion, the class C must
contain circuits with t outputs (otherwise, for a circuit C with much fewer out-
puts, the conditional entropy H(f (x1 ), ..., f (xt )|C(x1 , ..., xt )) is large merely due
to information theoretical reasons). On the other hand, the more outputs the
circuits in C have, the stronger the hypothesis of Proposition 11 is. In particular,
the number of outputs must be smaller that |X| otherwise the value of the circuit
C(x) = x determines f (x) (i.e., H(f (x)|x) = 0). Thus, a natural instantiation
of Proposition 11 is for a family of small (e.g., poly-size) circuits each having t
outputs.
20

Proof: By definition of conditional entropy, we have for every C C,

H(f (X (1) ), ..., f (X (t) )|C(X (1) , ..., X (t) ))

X t
= H(f (X (i) )|C(X (1) , ..., X (t) ), f (X (1) ), ..., f (X (i1) ))
i=1
t
X
H(f (X (i) )|C(X (1) , ..., X (t) ), X (1) , ..., X (i1) ).
i=1

Now, for each i, we show that

H(f (X (i) )|C(X (1) , ..., X (t) ), X (1) , ..., X (i1) ) .

We consider all possible settings of all variables, except X (i) , and bound the
conditional entropy under this setting (which does not effect X (i) ). The fixed
values X (j) = xj can be eliminated from the entropy condition and incorporated
into the circuit. However, fixing some of the inputs in the circuit C yields a
circuit also in C and so we can apply the propositions hypothesis and get

H(f (X (i) )|C(x1 , ..., xi1 , X (i) , xi+1 , ..., xt )) .

The proposition follows.

Proposition 11 vs the Concatenation Lemma. We compare the hypotheses

and conclusions of these two results.

The hypotheses. The hypothesis in Proposition 11 is related to the hypotheses

in the Concatenation Lemma. Clearly, an entropy lower bound (on a single
bit) translates to some unpredictability bound on this bit. (This does not
hold for many bits as can be seen below.) The other direction (i.e., unpre-
dictability implies a lower bound on the conditional entropy) is obvious for
a single bit.
The conclusions. For t = O(log n) the conclusion of Proposition 11 is implied
by the conclusion of the Concatenation Lemma, but for sufficiently large t the
conclusion of Proposition 11 does not imply the conclusion of Concatenation
Lemma. Details follow.
1. To show that, for t = O(log n), the conclusion of the Concatenation
Lemma implies the conclusion of Proposition 11, suppose that for a small
def
circuit C it holds that h = H(f (X (1) ), ..., f (X (t) )|C(X (1) , ..., X (t) )) =
o(t). Then, for every value of C, denoted v, there exists a string w = w(v)
such that Prob[f (X (1) ), ..., f (X (t) ) = w|C(X (1) , ..., X (t) ) = v] 2h . Hard-
wiring these 2t strings w() into C, we obtain a small circuit that predicts
f (X (1) ), ..., f (X (t) ) with probability at least 2h = 2o(t) , in contradic-
tion to the conclusion of the Concatenation Lemma.
2. To show that the conclusion of Proposition 11 does not imply the con-
clusion of the Concatenation Lemma, consider the possibility of a small
 21

(randomized) circuit C that with probability 1 correctly determines all

the f values (i.e., Prob[C(X (1) , ..., X (t) ) = f (X (1) ), ..., f (X (t) )] = 1 ),
and yields no information (e.g., outputs a special fail symbol) otherwise.
Then, although C has success probability 1 , the conditional entropy
is (1 ) 0 + t (assuming that Prob[f (X) = 1] = 1/2).

7 Subsequent Work

Since the first publication of this survey, Yaos XOR Lemma has been the subject
of intensive research. Here we only outline three themes that were pursued, while
referring the interested reader to [10] and the references therein.

Derandomization. A central motivation for Impagliazzos work [7, 8] has been the
desire to present derandomized versions of the XOR Lemma; that is, predi-
cates that use their input in order to define a sequence of related instances,
and take the XOR of the original predicate on these instances.12 The potential
benefit in such a construction is that the hardness of the resulting predicate is
related to shorter inputs (i.e., the seed of a generator of a t-long sequence of n-bit
long strings, rather than the tn-bit long sequence itself). Indeed, Impagliazzos
work [7, 8] presented such a construction (based on a pairwise independent gen-
erator), and left the question of providing a full derandomization (that uses a
seed of length O(n) to generate t instances) to subsequent work. The goal was
achieved by Impagliazzo and Wigderson [11] by using a generator that combines
Impagliazzos generator [7, 8] with a new generator, which in turn combines an
expander walk generator with the Nisan-Wigderson generator [15].

Avoiding the use of random examples. As pointed out in Section 2.3, all proofs
presented in this survey make an essential use of random examples. For more
than a decade, this feature stood in the way of a general uniform version of
the XOR Lemma (i.e., all uniform proofs assumed access to such random exam-
ples). This barrier was lifted by Impagliazzo, Jaiswal, and Kabanets [9], which
culminated in comprehensive treatment of [10]. The latter work provides sim-
plified, optimized, and derandomized versions of the XOR and Concatenation
Lemmas.13 The key idea is to use the hypothetical solver of the concatenated
problem in order to obtain a sequence of random examples that are all good
with noticeable probability. An instance of the original problem is then solved
by hiding it in a random sequence that has a fair intersection with the initial
12
That is, the predicate consists of an instance generator and multiple applications
of the original predicate, P . Specifically, on input an s-bit long seed, denoted y, the
generator produces a t-long sequence of n-bit long strings (i.e., (x1 , ..., xt ) G(y)),
and the value of the new predicate is defined as the XOR of the values of P on these
t strings (i.e., ti=1 P (xi )).
13
The focus of [10] is actually on the Concatenation Lemma, which is currently called
the Direct Product Theorem. See next paragraph regarding the relation to the XOR
Lemma.
22

sequence of random examples. The interested reader is referred to [10] for a

mature description of this idea (and its sources of inspirarion) as well as for a
discussion of the relation this problem (i.e., proofs of the Concatenation Lemma)
and list-decoding of the direct product code.

The relation between the XOR and Concatenation Lemmas. In Section 5 we

advocated deriving the XOR Lemma from the Concatenation Lemma, and this
suggestion was adopted in several works (including [9, 10]). Our intuition that
the Concatenation Lemma is simpler than the XOR Lemma is supported by a
recent work of Viola and Wigderson, which provides a very simple proof that,
in the general setting, the XOR Lemma implies the Concatenation Lemma [16,
Prop. 1.4]. We mention that the both directions of the equivalence between
the Concatenation Lemma and the XOR Lemma pass through an intermedi-
ate lemma called the Selective XOR Lemma (see [4, Exer. 7.17]). For further
discussion see Appendix B.

Acknowledgement
We wish to thank Mike Saks for useful discussions regarding Levins proof of the
XOR Lemma. We also thank Salil Vadhan and Ronen Shaltiel for pointing out
errors in previous versions, and for suggesting ways to fix these errors.

References
1. O. Goldreich. Foundation of Cryptography Class Notes. Spring 1989, Computer
Science Department, Technion, Haifa, Israel.
2. O. Goldreich. Foundation of Cryptography Fragments of a Book. February
1995. Available from ECCC.
3. O. Goldreich. Foundation of Cryptography: Basic Tools. Cambridge University
Press, 2001.
4. O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge
University Press, 2008.
5. O. Goldreich and L.A. Levin. A Hard-Core Predicate for all One-Way Functions.
In 21st STOC, pages 2532, 1989.
6. J. H
astad, R. Impagliazzo, L.A. Levin and M. Luby. A Pseudorandom Generator
from any One-way Function. SICOMP, Volume 28, Number 4, pages 13641396,
1999. Combines papers of Impagliazzo et al. (21st STOC, 1989) and H astad
(22nd STOC, 1990).
7. R. Impagliazzo, manuscript 1994. See [8], which appeared after our first posting.
8. R. Impagliazzo. Hard-core Distributions for Somewhat Hard Problems. In 36th
FOCS, pages 538545, 1995. This is a later version of [7].
9. R. Impagliazzo, R. Jaiswal, and V. Kabanets Approximately List-Decoding
Direct Product Codes and Uniform Hardness Amplification. In 47th FOCS,
pages 187196, 2006.
10. R. Impagliazzo, R. Jaiswal, V. Kabanets, and A. Wigderson: Uniform Direct
Product Theorems: Simplified, Optimized, and Derandomized. SIAM J. Com-
put., Vol. 39 (4), pages 16371665, 2010. Preliminary version in 40th STOC,
2008.
 23

11. R. Impagliazzo and A. Wigderson. P=BPP if E requires exponential circuits:

Derandomizing the XOR Lemma. In 29th STOC, pages 220229, 1997.
12. L.A. Levin. One-Way Functions and Pseudorandom Generators. Combinatorica,
Vol. 7, No. 4, pages 357363, 1987.
13. L.A. Levin. Average Case Complete Problems. SICOMP, Vol. 15, pages 285286,
1986.
14. N. Nisan, S. Rudich, and M. Saks. Products and Help Bits in Decision Trees.
In 35th FOCS, pages 318329, 1994.
15. N. Nisan and A. Wigderson. Hardness vs Randomness. JCSS, Vol. 49, No. 2,
pages 149167, 1994.
16. E. Viola and A. Wigderson. Norms, XOR Lemmas, and Lower Bounds for
Polynomials and Protocols. Theory of Computing, Vol. 4 (1), pages 137168,
2008. Preliminary version in IEEE Conf. on Comput. Complex., 2007.
17. A.C. Yao. Theory and Application of Trapdoor Functions. In 23st FOCS, pages
8091, 1982.

Appendix A: Proof of a Generalization of Lemma 6

We first generalize Impagliazzos treatment to the case of non-uniform distribu-
tions; Impagliazzos treatment is regained by letting X be the uniform probabil-
ity ensemble.

Definition 3 (hard-core of a predicate relative to a distribution): Let f : {0, 1}

{0, 1} be a Boolean predicate, s : N N be a size function, : N [0, 1] be a func-
tion, and X = {Xn } be a probability ensemble.
We say that a sequence of sets, S = {Sn {0, 1}n}, is a hard-core of f
relative to X with respect to s()-size circuits families and advantage () if
for every n and every circuit Cn of size at most s(n), it holds that
1
Prob[Cn (Xn ) = f (Xn )|Xn Sn ] + (n).
2
We say that f has a hard-core of density () relative to X with respect to
s()-size circuits families and advantage () if there exists a sequence of sets
S = {Sn {0, 1}n} such that S is a hard-core of f relative to X with respect
to the above and Prob[Xn Sn ] (n).

Lemma 12 (generalization of Lemma 6): Let f : {0, 1} {0, 1} be a Boolean

predicate, s : N N be a size function, X = {Xn } be a probability ensemble, and
: N [0, 1] be a noticeable function such that for every n and every circuit Cn
of size at most s(n), it holds that

Prob[Cn (Xn ) = f (Xn )] 1 (n).

Then, for every function : N [0, 1], the function f has a hard-core of density
() relative to X with respect to s ()-size circuits families and advantage (),
def def
where (n) = (1 o(1)) (n) and s (n) = s(n)/poly(n/(n)).
24

Proof: We start by proving a weaker statement; namely, that X dominates

an ensemble Y under which the function f is strongly unpredictable. Our notion
of domination originates in a different work of Levin [13]. Specifically, referring
to a fixed function , we define domination as assigning probability mass that is
at least a fraction of the mass assigned by the dominated ensemble; namely:
Definition: Fixing the function for the rest of the proof, we say that the ensemble
X = {Xn } dominates the ensemble Y = {Yn } if for every string ,

Prob[Xn = ] (||) Prob[Yn = ].

In this case we also say that Y is dominated by X. We say that Y is critically dom-
inated by X if for every string either Prob[Yn = ] = (1/(||)) Prob[Xn = ]
or Prob[Yn = ] = 0. (Actually, to avoid trivial difficulties, we allow at most one
string {0, 1}n such that 0 < Prob[Yn = ] < (1/(||)) Prob[Xn = ].)
The notions of domination and critical domination play central roles in the
following proof, which consists of two parts. In the first part (cf., Claim 12.1),
we prove the existence of a ensemble dominated by X such that f is strongly
unpredictable under this ensemble. In the second part (cf., Claims 12.2 and 12.3),
we essentially prove that the existence of such a dominated ensemble implies the
existence of an ensemble that is critically dominated by X such that f is strongly
unpredictable under the latter ensemble. However, such a critically dominated
ensemble defines a hard-core of f relative to X, and the lemma follows. Before
starting, we make the following simplifying assumptions (used in Claim 12.3).
Simplifying assumptions: Without loss of generality, the following two conditions
hold:
1. log2 s(n) n.
(Otherwise the hypothesis of the lemma cannot hold.)
2. Prob[Xn = x] < poly(n)/s(n), for all xs.
(This assumption is justified since xs violating this condition cannot con-
tribute to the hardness of f with respect to Xn , because one can incorporate
all these s(n)/poly(n) many violating xs with their corresponding f (x)s
into the circuit).

Claim 12.1: Under the hypothesis of the lemma it holds that there exists a prob-
ability ensemble Y = {Yn } such that Y is dominated by X and, for every
s (n)-circuit Cn , it holds that

1 (n)
Prob[Cn (Yn ) = f (Yn )] + (5)
2 2 .
Proof:14 We start by assuming, towards the contradiction, that for every distri-
bution Yn that is dominated by Xn there exists an s (n)-size circuits Cn such
that Prob[Cn (Yn ) = f (Yn )] > 0.5 + (n), where (n) = (n)/2. One key obser-
vation is that there is a correspondence between the set of all distributions that
14
The current text was revised following the revision in [4, Sec. 7.2.2.1].
 25

are each dominated by Xn and the set of all the convex combinations of criti-
cally dominated (by Xn ) distributions; that is, each dominated distribution is a
convex combinations of critically dominated distributions and vice versa. Thus,
(1) (t)
considering an enumeration Yn , ..., Yn of all the critically dominated (by Xn )
distributions, we conclude that, for every distribution (or convex combination)
on [t], there exists an s (n)-size circuits Cn such that
t
X
(i) Prob[Cn (Yn(i) ) = f (Yn(i) )] > 0.5 + (n). (6)
i=1

Now, consider a finite game between two players, where the first player selects
a critically dominated (by Xn ) distribution, and the second player selects an
s (n)-size circuit and obtains a payoff as determined by the corresponding suc-
cess probability; that is, if the first player selects the ith critically dominated
distribution and the second player selects the circuit C, then the payoff equals
(i) (i)
Prob[C(Yn ) = f (Yn )]. Taking this perspective Eq. (6) means that, for any
randomized strategy for the first player, there exists a deterministic strategy for
the second player yielding average payoff greater than 0.5 + (n). The Min-Max
Principle asserts that, in such a case, there exists a randomized strategy for
the second player that yields average payoff greater than 0.5 + (n) no matter
what strategy is employed by the first player. This means that there exists a
distribution, denoted Dn , on s (n)-size circuits such that for every i it holds
that
Prob[Dn (Yn(i) ) = f (Yn(i) )] > 0.5 + (n), (7)
where the probability refers both to the choice of the circuit Dn and to the
(i)
random variable Yn . Let Bn = {x : Prob[Dn (x) = f (x)] 0.5 + (n)}. Then,
Prob[Xn Bn ] < (n), because otherwise we reach a contradiction to Eq. (7) by
defining Yn such that Prob[Yn = x] = Prob[Xn = x]/Prob[Xn Bn ] if x Bn and
Prob[Yn = x] = 0 otherwise.15 By employing standard amplification to Dn , we
obtain a distribution Dn over poly(n/ (n))s (n)-size circuits such that for every
x {0, 1}n \ Bn it holds that Prob[Dn (x) = f (x)] > 1 2n . It follows that there
exists an s(n)-sized circuit Cn such that Cn (x) = f (x) for every x {0, 1}n \ Bn ,
which implies that Prob[Cn (Xn ) = f (Xn )] Prob[Xn {0, 1}n \ Bn ] > 1 (n),
in contradiction to the theorems hypothesis. The claim follows.

From a dominated ensemble to a hard-core. In the rest of the proof, we fix

an arbitrary ensemble, denoted Y = {Yn } satisfying Claim 12.1. Using this
ensemble, which is dominated by X, we prove the validity of the lemma (i.e., the
existence of a hard-core) by a probabilistic argument. Specifically, we consider
the following probabilistic construction.
15
Note that Yn is dominated by Xn , whereas by the hypothesis Prob[Dn (Yn ) =
f (Yn )] 0.5 + (n). Using the fact that any dominated distribution is a convex
(i)
combination of critically dominated distributions, it follows that Prob[Dn (Yn ) =
(i) (i)
f (Yn )] 0.5 + (n) holds for some critically dominated Yn .
26

Probabilistic construction: We define a random set Rn {0, 1}n by selecting each

string x {0, 1}n to be in Rn with probability

def (n) Prob[Yn = x]

p(x) = 1 (8)
Prob[Xn = x]

independently of the choices made for all other strings. Note that the inequality
holds because X dominates Y.
First we show that, with overwhelmingly high probability over the choive of
Rn , it holds that Prob[Xn Rn ] (n).
Claim 12.2: Let > 0 and suppose that Prob[Xn = x] (n) 2 /poly(n), for
every x. Then, for all but at most a 2poly(n) measure of the choices of Rn , it
holds that
|Prob[Xn Rn ] (n)| < (n).
def
Proof: For every x {0, 1}n, let wx = Prob[Xn = x]. We define random variables
x = x (Rn ), over the probability space defined by the random choices of Rn ,
such that x indicate whether x Rn ; that is, the x s are independent of one
another, and Prob[x = 1] = p(x) (and x = 0 otherwise). Thus, for every possible
choice of Rn , it holds that
X
Prob[Xn Rn ] = x (Rn ) wx
x
P
and consequently we are interested in the behaviour of the sum x wx x as a
random variable (over the probability space of all possible choices of Rn ). Taking
expactation (over the possible choices of Rn ), we get
" #
X X
E wx x = p(x) wx
x x
X (n) Prob[Yn = x]
= Prob[Xn = x]
x
Prob[Xn = x]
= (n).

Now, using Chernoff bound, we get

"  #
2 (n)
X    
Prob  wx x (n) > (n) < exp
 

x
 maxx {wx } .

Finally, using the claims hypotheses wx 2 (n)/poly(n) (for all xs), the
latter expression is bounded by exp(poly(n)), and the claim follows.

Finally, we show that Rn is likely to be a hard-core of f realtive to X (w.r.t.

sufficiently small circuits).
 27

Claim 12.3:16 For all but at most a 2poly(n) measure of the choices of Rn , it
holds that every circuit Cn of size s (n) satisfies

1
Prob[Cn (Xn ) = f (Xn )|Xn Rn ] < + (n).
2
Proof: We define the same random variables x = x (Rn ) as in the proof of
Claim 12.2; that is, x (Rn ) = 1 if x Rn and x (Rn ) = 0 otherwise. Also, as
def
before, wx = Prob[Xn = x], for every x {0, 1}n. Fixing any circuit Cn , let C
be the set of inputs on which Cn correctly computes f ; namely,
def
C = {x : Cn (x) = f (x)}. (9)

For every choice of Rn , we are interested in the probability

Prob[Xn C Xn Rn ]
Prob[Xn C|Xn Rn ] = (10)
Prob[Xn Rn ] .

We first determine the expected value of the numerator of Eq. (10), where the
expactation
P is taken over the possible choices of Rn . We rewrite the numerator
as xC x (Rn ) wx , and lower bound it as follows
" #
X X
E x wx = p(x) wx
xC xC
X (n) Prob[Yn = x]
= Prob[Xn = x]
Prob[Xn = x]
xC
= (n) Prob[Yn C]
 
1 (n)
(n) +
2 2 ,

where the last inequality is due to the hypothesis regarding Yn . Next, we use a
(multiplicative) Chernoff bound, and get
" # !!
  2
X 1 2(n) (n) (n)
Prob wx x > + (n) < exp
2 3 maxx {wx }
xC
!!
2
(n) s(n) log2 s(n)
< exp
poly(n)
,

where the last inequality uses the simplifying assumptions regarding the wx s
and s(n) (i.e., wx < poly(n)/s(n) and log2 s(n) n). Thus, for all but at most
a exp(poly(n) s (n) log2 s (n)) measure of the Rn s, the numerator of Eq. (10)
is at most ( 21 + 2(n)
3 ) (n). This holds for each possible circuit of size s (n).
16
The current statement and its proof were somewhat revised.
28

Applying the union bound to the set of all 2s (n)(O(1)+2 log2 s (n)) possible circuits
of size s (n), we conclude that the probability that for some of these circuits the
numerator of Eq. (10) is greater than ( 21 + 2(n)
3 ) (n) is at most exp(poly(n)),
where the probability is taken over the choice of Rn . Using Claim 12.2, we
conclude that, for a similar measure of Rn s, the denumerator of Eq. (10) is at
least (1 (n)
3 ) (n). The claim follows.

Conclusion. The lemma now follows by combining the foregoing three claims.
Claim 12.1 provides us with a suitable Y for which we apply the probabilistic
construction, whereas Claims 12.2 and 12.3 establish the existence of a set Rn
such that both
Prob[Xn Rn ] > (1 o(1)) (n)
and
1
Prob[Cn (Xn ) = f (Xn )|Xn Rn ] < + (n)
2
holds for all possible circuits, Cn , of size s (n). The lemma follows.

Appendix B: On the Selective XOR Lemma

Following [4, Exer. 7.17], we explicitly introduce a variant of the XOR Lemma,
called the Selective XOR Lemma. Recall that the standard XOR Lemma refers to
def Qt(n)
the predicate P (t) (x1 , ..., xt(n) ) = i=1 P (xi ), where P is the original predicate
and xi {0, 1}n for every i. Instead, the Selective XOR Lemma refers to the
def Q
predicate Q(t) (x1 , ..., xt(n) , S) = iS P (xi ), where the xi s are as before and
S {1, ..., t(n)} is represented as an t(n)-bit long string. Thus, we have the
following variant of Lemma 1.
Lemma 13 (Selective XOR Lemma): Let P and X = {Xn } be as in Defini-
tion 1. For every function t : N N, define the predicate
def
Y
Q(t) (x1 , ..., xt(n) , S) = P (xi ) ,
iS

def (t)
where x1 , ..., xt(n) {0, 1}n and S {1, ..., t(n)}. Let Y(t) = {(Xn , Ut(n) )},
(t)
where Xn is as in Lemma 1 and Ut(n) be a random variable that is independently
and uniformly distributed over {0, 1}t(n).
(hypothesis) As in Lemma 1; that is, suppose that for some function s : N N
and some bounded-away-from-1 function : N [1, +1], it holds that is
an upper bound on the correlation of families of s()-size circuits with P over
X.
(conclusion) Analogously to Lemma 1, there exists a bounded-away-from-1 func-
tion : N [1, +1] and a polynomial p such that, for every function
t : N N and every function : N [0, 1], the function
def
(t) (n) = p(n) (n)t(n) + (n)
 29

is an upper bound on the correlation of families of s ()-size circuits with Q(t)

over Y(t) , where
 
def (n)
s (t(n) n) = poly s(n) poly(n t(n)).
n

In this appendix we discuss the relation of the Selective XOR Lemma to the
XOR Lemma and to the Concatenation Lemma.

The Selective XOR Lemma vs the Concatenation Lemma. As shown in Sec-

tion 5.2, the Concatenation Lemma implies the Selective XOR Lemma (by us-
ing Lemma 9). The opposite implication was recently shown in [16, Prop. 1.4].
The proof boils down to showing that any algorithm that computes the con-
catenation of the t values, can be used to correlate the selective XOR as fol-
lows: On input (x1 , ..., xt , S), we obtain (from the algorithm) a guess (b1 , ..., bt )
def Q
for (P (x1 ), ..., P (xt )), and output b(S) = iS bi . Note that if (b1 , ..., bt ) =
(P (x1 ), ..., P (xt )), then our answer b(S)Qis correct for any S, whereas if (b1 , ..., bt ) 6=
(P (x1 ), ..., P (xt )), then ProbS [b(S) = iS P (xi )] = 1/2. Thus, if the algorithm
is correct with probability p, then our answer has correlation p with Q(t) .

The Selective XOR Lemma implies the XOR Lemma. This implication was
sketched in Section 5.2, and we provide more details next. We show how to
use an algorithm that correlates P (t) in order to correlate Q(t) . We shall use t
random examples, denoted (z1 , P (z1 )), ..., (zt , P (zt )). On input (x1 , ..., xt , S), we
set xi = xi if i S and xi = zi otherwise, obtain (from the algorithm) a guess
b for P (t) (x1 , ..., xt ), and output b i[t]\S P (zi ). Thus, our answer is correct if
Q
(t) (t) (t)
Q only if b = P (x1 , ..., xt ), because P (x1 , ..., xt ) equals Q (x1 , ..., xt , S)
and
i[t]\S P (zi ).

The XOR Lemma implies the Selective XOR Lemma. Following [16, Prop. 1.4],
we show how to use an algorithm that correlates Q(3t) in order to correlate
P (t) . Here we shall use 3t random examples, denoted (z1 , P (z1 )), ..., (z3t , P (z3t )).
On input (x1 , ..., xt ), we select at random a subset S {1, ..., 3t}, and let
i1 , ..., it be arbitrary t distinct elements of S (assuming that |S| t). Next,
we set xij = xj for every j = 1, .., t, and set xi = zi for every i S , where
def
S = {1, ..., 3t} \ {ij : j = 1, ..., t}. WeQobtain (from the algorithm) a guess b
for Q(3t) (x1 , ..., x3t , S), and output b iS\S P (zi ). Thus, our answer is cor-
rect if and only Q if b = Q(3t) (x1 , ..., x3t , S), because Q(3t) (x1 , ..., x3t , S) equals
(t)
P (x1 , ..., xt ) iS\S P (zi ). Note that this works assuming that |S| t,
which holds with probability 1 2(t). Thus, our correlation with P (t) is lower
bounded by p 2(t) , where p is the correlation of the given algorithm with
Q(3t) .