2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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). $\endgroup$
    – Ariel
    Commented Mar 20, 2018 at 23:16
  • $\begingroup$ I'm talking good old deterministic Turing reduction. Find $x$ from $f(x)$ using a polynomial number of calls to $b$. $\endgroup$
    – Sebastian Oberhoff
    Commented Mar 20, 2018 at 23:18
  • $\begingroup$ 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. $\endgroup$
    – Ariel
    Commented Mar 20, 2018 at 23:22
  • $\begingroup$ 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) $\endgroup$
    – D.W. ♦
    Commented Mar 21, 2018 at 0:30
  • $\begingroup$ 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$.) $\endgroup$
    – D.W. ♦
    Commented Mar 21, 2018 at 0:31

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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