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$?

cs.stackexchange https://cs.stackexchange.com/questions/89601

  •  05-11-2019
  •  | 
  •  

سؤال

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.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top