[GL89] A Hard-Core Predicate for All One-Way Functions

Authors: Oded Goldreich, Leonid A. Levin | Venue: STOC 1989 | Source

Abstract

We prove that every one-way function has a hard-core predicate: a Boolean function $b(x)$ such that, given $f(x)$, no efficient algorithm can predict $b(x)$ with probability noticeably better than $1/2$. Specifically, for any one-way function $f$, the inner-product bit $b(x,r)=⟨x,r⟩(\mathrm{mod}2)$ is hard-core for the function $g(x,r)=(f(x),r)$, where $r$ is a uniformly random string of the same length as $x$. This result is the key step in the construction of a pseudorandom generator from any one-way function (see HILL99): the hard-core predicate provides a single pseudorandom bit, which can then be stretched into a full pseudorandom string.