Suppose are mutually independent unbiased random variables. Then we know everything about the distribution of
either by using the central limit theorem or by doing calculations by hand using binomial coefficients and Stirling’s approximation. In particular, we know that (1) takes the values with probability each, and so with constant probability (1) is at most .
The last statement can be proved from scratch using only pairwise independence. We compute
It is also true that (1) is at least with constant probability, and this is trickier to prove.
First of all, note that a proof based on pairwise independence is not possible any more. If is a random row of an Hadamard matrix, then with probability , and with probability .
Happily, four-wise independence suffices.
Lemma 1 Suppose are four-wise independent random variables. Then
This is probably well known to a lot of people, but the only place where I have seen this result is a paper by Andreev et al. that I have mentioned before.
Here is a slightly simplified version of their argument. We compute
So we have (from here on is our simplified version)
Following the same proof, but replacing each “” with “” and every “” with “”, we get the more general version
Lemma 2 Suppose are four-wise independent random variables and let be any real numbers. Then
A related version that was useful in our work on distinguishers for pseudorandom generators is
Corollary 3 Let be a four-wise independent family of functions and be any real valued function. Then
To briefly show how this relates to our work on distinguishers, suppose is a length-increasing function, and that we want to construct a function , computable by a circuit as small as possible, such that
Then this is equivalent to proving
and, if we set
then (2) is equivalent to
Now, fix a simple partition of into subsets each of size , for example based on the value of the first bits.
Fix an efficiently computable four-wise independent family of functions . Then we have, for every set in the partition
and if we sum over all sets in the partition we have
In particular, there is a function such that
To finish the argument, define the function such that iff , where is the set that belongs to. Then
- depends only on the first bits of the input, and so it can be computed by a circuit of size
- for every we have
So, in conclusion
meaning that setting satisfies (3), and gives us a distinguisher obtaining advantage and having circuit complexity .