** Summary **

Today we prove the Goldreich-Levin theorem.

**1. Goldreich-Levin Theorem **

We use the notation

**Theorem 1 (Goldreich and Levin)** * Let be a permutation computable in time . Suppose that is an algorithm of complexity such that*

*
*

Then there is an algorithm of complexity at most such that

* *

Last time we proved the following partial result.

**Lemma 2** * Suppose we have access to a function such that, for some unknown , we have*

*
*

where is an unknown string.

*
Then there is an algorithm that runs in time and makes oracle queries into and, with probability at least , outputs . *

This gave us a proof of a variant of the Goldreich-Levin Theorem in which the right-hand-side in (2) was . We could tweak the proof Lemma 2 so that the right-hand-side of (4) is , leading to proving a variant of the Goldreich-Levin Theorem in which the right-hand-side in (2) is also .

We need, however, the full Goldreich-Levin Theorem in order to construct a pseudorandom generator, and so it seems that we have to prove a strengthening of Lemma 2 in which the right-hand-side in (4) is .

Unfortunately such a stronger version of Lemma 2 is just false: for any two different we can construct an such that

and

so no algorithm can be guaranteed to find given an arbitrary function such that , because need not be uniquely defined by .

We can, however, prove the following:

**Lemma 3 (Goldreich-Levin Algorithm)** * Suppose we have access to a function such that, for some unknown , we have*

*
*

where is an unknown string, and is given.

*
Then there is an algorithm that runs in time and makes oracle queries into and, with probability at least , outputs a set such that and . *

The Goldreich-Levin Theorem is an easy consequence of Lemma 3. The Goldreich-Levin algorithm has other interpretations (an algorithm that learns the Fourier coefficients of , an algorithm that decodes the Hadamard code is sub-linear time) and various applications outside cryptography.

### Like this:

Like Loading...

*Related*