I'm working with this definition for one-way functions:
We call f a (strong) one-way function if
- it is computable in polynomial time
- for any polynomial time randomized algorithm B and any constant c P(f(B(f(x)))=f(x))=o(n−c) where x∈{0,1}n.
And this defintion for hard-core bits:
Let f:{0,1}n→{0,1}k and b:{0,1}n→{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, P(B(f(x))=b(x))=12+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: finding x reduces to finding b(x)⟹(f is one-way⟹b is hard-core) Or by contrapositive: finding x reduces to finding b(x)⟹(b isn't hard-core⟹f isn't one-way)
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(xi) where the xi are arbitrarily correlated.