# Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$?

I'm working with this definition for one-way functions:

We call $f$ a (strong) one-way function if

1. it is computable in polynomial time
2. for any polynomial time randomized algorithm $B$ and any constant $c$ $$\mathbb{P}\big(f(B(f(x))) = f(x)\big) = o(n^{-c})$$ where $x\in\{0,1\}^n.$

And this defintion for hard-core bits:

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})\,.$$

And I'm asking myself whether, if $f$ is one-way and finding $x$ from $f(x)$ is polynomial time reducible to finding $b(x)$ from $f(x)$, $b$ must be hard-core. One way to structure this argument is like so: $$\text{finding x reduces to finding b(x)} \implies \big(f\text{ is one-way} \implies b\text{ is hard-core}\big)$$ Or by contrapositive: $$\text{finding x reduces to finding b(x)} \implies \big(b\text{ isn't hard-core} \implies f\text{ isn't one-way}\big)$$

So suppose finding $x$ reduces to finding $b(x)$ and $b$ isn't hard-core. Then the obvious strategy is to go through the reduction but instead of computing $b(x)$ deterministically, we make a good guess using some algorithm $B$ which must exist because $b$ isn't hard-core. Since we have a non-negligible chance of success to guess $b(x)$ correctly, we end up with a non-negligible chance to guess $x$ correctly and so $f$ isn't one-way.
But there's a point here where trouble comes in. That is, the reduction might involve computing $b(x)$ multiple times for various values of $x$. While we know the probability of computing a single $b(x)$ for a random $x$ correctly, I don't have any handle on the probability of success for a sequence of calls $b(x_i)$ where the $x_i$ are arbitrarily correlated.

• You have to define your notion of reduction. If we're talking about a machine with oracle to $h(x)$ given $f(x)$ (i.e. your reduction is to recovering $h$ on the worst case) then this is not obvious. If however average case success will do, then $h$ is hardcore (my comments in your other question show that $b$ cannot be found with high probability on the worst case, which is weaker than being hc). – Ariel Mar 20 '18 at 23:16
• I'm talking good old deterministic Turing reduction. Find $x$ from $f(x)$ using a polynomial number of calls to $b$. – Sebastian Oberhoff Mar 20 '18 at 23:18
• Note that the problem is not different evaluations, even a single evaluation might kill you if you only assume $h$ is easy on average. If $h$ was easy on the worst case (even with success probability slightly greater than $\frac{1}{2}$), then you were fine by amplification and using the union bound. – Ariel Mar 20 '18 at 23:22
• Whether you can prove it depends on the specific nature of the reduction, and in some sense whether $f,b$ are randomized or deterministic. I suggest working through the statement and proof of the Goldreich-Levin theorem. That gives a worked example of this kind of reasoning. Then, see how it applies here. That should give you a better understanding. (continued) – D.W. Mar 21 '18 at 0:30
• There, we show that if we had an algorithm $A$ that can predict $b(x)$ from $f(x)$, we could construct a new algorithm to predict $x$ from $f(x)$, by repeatedly invoking $A$. (Why can we repeatedly invoke $A$ without getting the same answer every time? Because of the specific properties of the one-way function and hardcore predicate considered in the Goldreich-Levin theorem, specifically, $f(x)$ has the form $f(x_1,x_2) = (x_1,f_2(x_2))$. Thus given $f(x)=(x_1,y_1)$ we can run $A$ on many inputs $(x'_1,y_1)$ and use that to draw inferences about $x_2$ and thus $x$.) – D.W. Mar 21 '18 at 0:31

Before addressing your question, we should note that there are some subtleties when defining "inverting $f(x)$ reduces to finding $h(x)$". Suppose we aim towards something along the lines of a standard Turing reduction, then what does our oracle do? When feeding the oracle some string $y\in\{0,1\}^*$, where the only promise about $y$ is that it lies in the image of $f$, then what do you expect it to return? If $f$ is a permutation, then this is easy. However, when $f$ is not one to one, it isn't clear what to expect. One possibility is to require that the oracle returns $h(x)$ for some $x\in f^{-1}(y)$, though it might make the oracle pretty much useless (I'd guess that there exists a one way function $f$ and a hardcore predicate $h$ for $f$ such that any function in $2^{\{0,1\}^*}$ is an $h$-oracle for $f$ under this definition).
Back to your original question. Suppose $f$ is a one way permutation and define $g(x,i,j)=(f(x),i,j,x_i)$. Inverting $f$ reduces to (under the above definition) evaluating $h(x,i,j)=x_j$, since you can feed the oracle different values of $j$. However, $h$ is not hardcore for $g$, since for a uniformly chosen triplet $(x,i,j)$ where $x\in\{0,1\}^n$ and $i,j\in [n]$, with probability $\frac{1}{n}$ it holds that $i=j$ and you can recover $x_j$.