A generic hardcore predicate for any one-way function

Webpage for a paper by Oded Goldreich and Leonid Levin

Material avialable on-line

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.