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?


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$).

  • $\begingroup$ Is there any hope for the other direction though? $\endgroup$ Mar 20 '18 at 8:40
  • $\begingroup$ Not really, if $f$ is "very" not one to one then finding an inverse might not help you compute $h$, take a constant function for example. $\endgroup$
    – Ariel
    Mar 20 '18 at 9:05
  • $\begingroup$ I'm asking suppose finding $x$ was reducible to finding $b(x)$, does that make $b$ a hard-core predicate? I don't see how what you said has any bearing on that. $\endgroup$ Mar 20 '18 at 9:18
  • $\begingroup$ My last comment referred to the opposite reduction, whether evaluating $h$ is always reducible to finding an inverse. As for your last comment, the answer is yes. If $f$ is one-way and inverting it is reducible to evaluating $h$, in the sense that there exists a polynomial time machine with access to an $h(f(x))$ oracle which inverts $f$ with non negligible probability, then $h$ is hardcore for $f$. cont... $\endgroup$
    – Ariel
    Mar 20 '18 at 18:17
  • $\begingroup$ To see why, suppose you can evaluate $h$ infinitely often with probability at least $\frac{1}{2}+n^{-c}$, then for those values of $n$, after enough amplification, you can simulate the oracle machine while replacing oracle calls with the algorithm for $h$. Conditioning on the event that all of the computations of $h$ during the simulation returned the right answer, you will be able to invert $f$ with non negligible probability. I leave the details to you. $\endgroup$
    – Ariel
    Mar 20 '18 at 18:23

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.