Timeline for 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$?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2018 at 16:09 | vote | accept | Sebastian Oberhoff | ||
| Apr 3, 2018 at 11:50 | answer | added | Ariel | timeline score: 2 | |
| Mar 21, 2018 at 0:31 | comment | added | D.W.♦ | 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$.) | |
| Mar 21, 2018 at 0:30 | comment | added | D.W.♦ | 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) | |
| Mar 20, 2018 at 23:22 | comment | added | Ariel | 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. | |
| Mar 20, 2018 at 23:18 | comment | added | Sebastian Oberhoff | I'm talking good old deterministic Turing reduction. Find $x$ from $f(x)$ using a polynomial number of calls to $b$. | |
| Mar 20, 2018 at 23:16 | comment | added | Ariel | 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). | |
| Mar 20, 2018 at 22:54 | history | asked | Sebastian Oberhoff | CC BY-SA 3.0 |