Applications of the Goldreich-Levin Theorem

Russell Impagliazzo
University of California at San Diego

The Goldreich-Levin Theorem was originally phrased as a
universal method for finding unpredictible input bits
for one-way functions. However, it is much more than
that. We'll sketch several ways of viewing this result:
from the cryptographic viewpoint, in learning theory,
and as a list decoding algorithm for error-correcting
codes. Then we'll present several applications of this
result: in the foundations of cryptography; analyzing
specific pseudo-random generators; to extractors, a
way of removing biases from flawed sources of
randomness; and to derandomization, simulation of
randomized algorithms deterministically. We'll
sketch how the ideas behind this result have been
extended in recent work.

Back to Contemporary Methods in Cryptography