Under what circumstances are one-way functions reducible to their hard-core bits?

Question

I've seen competing claims about hard-core predicates. On the one hand, there's the basic definition

Let $f : \{0,1\}^n \rightarrow \{0,1\}^k$ and $b : \{0,1\}^n \rightarrow \{0,1\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$, $$ \mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\,. $$

But I've also read the statement

We want the problem of finding $x$ to be reducible, in polynomial time, to the problem of finding $b(x)$, so that finding $b(x)$ is just as hard as finding all of $x$. In that case $b$ is called a hard-core bit for $f$.

How are these requirements related? Is one stronger than the other? Or do they imply each other?

Answer 1

Inverting a one way function is not always reducible to evaluating a hardcore bit. As an example, consider trivial hardcore predicates. Let $f$ be one way and define $g(x,b)=f(x)$ where $b\in\{0,1\}$. Obviously $b$ (the rightmost bit of a string) is a hardcore predicate for $g$, however knowing it does not bring you any closer to finding the rest of the string. The problem is that such predicates are probably of no use. Usually, we cant afford to lose information (e.g. while constructing pseudorandom generators), so we won't be able to base hardcore predicates on a part of the input that we're not using.

To overcome the above problem (i.e. ignoring trivial hardcore predicates), we can demand that evaluating the predicate will help us reverse the function (if this is the case, then $f(x)$ and $h(x)$ cannot be independent). The generic construction in Goldreich-Levin's theorem indeed yields such a predicate. If $f$ is one way and $g(x,r)=(f(x),r)$, then an algorithm computing $h(x,r)=\langle x,r\rangle$ can be used to find $x$ (just feed it $f(x)$ along with different values of $r$).

Answer 2

An intuitive, informal interpretation of the first definition is that it is hard to find $b(x)$ (given $f(x)$). If you can predict $b(x)$ from $f(x)$, then you have an adversary $B$ such that $\mathbb{P}[B(f(x))=b(x)]$ is significantly larger than $1/2$; the assumption that no such adversary exists means that you cannot predict $b(x)$ from $f(x)$. Conversely, any such adversary gives a way to predict $b(x)$ from $f(x)$.

One way to show that it is hard to find $b(x)$ is to show that finding $x$ (from $f(x)$) reduces to finding $b(x)$ (from $f(x)$). The assumption that $f$ is one-way implies that finding $x$ (from $f(x)$) is hard. Such a reduction would then imply that finding $b(x)$ (from $f(x)$) is hard as well.

The Goldreich-Levin theorem shows one example of a specific predicate $b(x)$ where we can demonstrate the existence of such a reduction. That then implies that this predicate $b(x)$ is hardcore.

See https://en.wikipedia.org/wiki/Hard-core_predicate and a good textbook on one-way functions, hardcore predicates, and the Goldreich-Levin theorem.