- extended abstract, 21st STOC, 1989. (Copyright of ACM)
- Section 3 in Three XOR-Lemmas - An Exposition (1991).
- Appendix C.2 in
Modern Cryptography,
Probabilistic Proofs and Pseudorandomness (1998).

See extract. - Section 2.5 in Foundations of Cryptography
(Vol 1, 2001).

See extract.

A key tool in the construction of pseudorandom generators
is the construction of hard-core predicates.
A hard-core predicate of the function **f** is
a polynomial-time computable predicate of **x** which is hard to
approximate from **f(x)**.
Goldreich with Levin proved that any one-way function
of the form **f(x,r)=(f'(x),r)** has a hard-core predicate
(specifically, the inner-product mod~2 of **x** and **r**).

The above result played an important role in further development in the area of pseudorandomness. In particular, it yields a very simple construction of a pseudorandom generator based on any one-way permutation and was used (by Hastad, Impagliazzo, Levin and Luby) to construct a pseudorandom generator based on any one-way function. The above result improves over a previous general result of Yao and over previous results concerning specific functions of Blum and Micali, and Alexi, Chor, Goldreich and Schnorr.

Put in more general terms, the above result asserts
that the complexity of any search problem is related to the complexity
of answering ``random (linear) queries'' concerning the solution.
Namely, if it is infeasible,
on input **x**, to find **s** such that **(x,s)** in **R**
then its is infeasible to predict the inner-product (mod 2)
of **s** and **r**, when given **x** and **r**,
for a uniformly chosen **r**.
This general form found many additional applications.

Back to Oded Goldreich's homepage.