[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.

BibTeX

Copy

@Inproceedings{STOC:GolLev89,
  author = {Oded Goldreich and Leonid A. Levin},
  title = {A Hard-Core Predicate for all One-Way Functions},
  pages = {25--32},
  booktitle = {21st Annual {ACM} Symposium on Theory of Computing},
  address = {Seattle, WA, USA},
  month = {may~15--17},
  publisher = {{ACM} Press},
  year = {1989},
  doi = {10.1145/73007.73010},
}