# How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

I'm considering the following definition of one-way functions:

Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all polynomial-time randomized algorithms $A$ and all constants $c$, $$\underset{x\in\{0,1\}^k}{\mathbb{E}}\Big[\mathbb{P}[A(f(x))=b(x)]\Big]=\frac{1}{2}+o(k^{-c})$$

Note that $A(f(x))=b(x)$ is an event, not because $x$ is random but because $A$ is a randomized algorithm.
Now suppose $f$ isn't a one-way function, then this expectation will be noticeably different from $1/2$. But for any particular $x$ the probability might still be close to $1/2$. Indeed the probability could be exactly $1/2$ (or even 0) for a large fraction of the $x$, provided for the remaining $x$ $f(x)$ can be inverted with sufficient accuracy to make the expectation noticeably different from $1/2$ again.
So what do I do if I'm presented with such an $f(x)$? The fact that many other $f(x)$ can easily be inverted seems of little consolation then. I don't see any way to invert $f$ then. In particular in connection with pseudorandom number generators I'm reading statements like

We will show that if any tester $A$ can tell the difference between $g(x) = (f(x),\,b(x))$ and a random string, then we can use $A$ to "break" our one-way function, and calculate $b(x)$ from $f(x)$ with $1/\text{poly}(k)$ probability.

I can read this in two different ways.

1. $x$ is random and there's a $1/\text{poly}(k)$ chance of getting an $x$ for which $b(x)$ can be computed from $f(x)$ exactly.
2. For every $x$ $b(x)$ can be computed from $f(x)$ with a $1/\text{poly}(k)$ chance of success.

(1) has the problem that the text presents a randomized algorithm to compute $b(x)$ from $f(x).$ It isn't exact.
(2) is false based on the preceding discussion.

• What's the problem if the algorithm isn't exact? – xskxzr Mar 15 '18 at 3:16
• @xskxzr The quoted segment makes a probabilistic statement about either the runtime behaviour of some inversion procedure $B$ or the $x$ that's being considered. If you assume that it's the $x$ that's random then $B$ just computes $b(x)$ from $f(x)$. But that sounds like you're saying that $B$ is deterministic when it isn't. – Sebastian Oberhoff Mar 15 '18 at 3:29
• The first interpretation also doesn't make sense for the second reason that the text only establishes a claim about the expectation when $x$ is considered random. You can't draw a statement about probabilities from that. (Unless you use something like Markov's inequality. But that is never even hinted.) – Sebastian Oberhoff Mar 15 '18 at 3:34

Both (1) and (2) are possible. (It's also possible to have a combination of them.) It doesn't really matter which holds; either way, that means that $f$ is not one-way.

You say (2) is false because of the preceding discussion, but I'm not exactly sure why you think it is false. One-wayness is not a property of a specific value of $x$; rather, it is a property of a function $f$. And, just because a function $f$ is not one-way doesn't mean it can be inverted for every possible output. If $f$ can be inverted on a significant fraction of outputs, it is not one-way. If $f$ can be inverted on all outputs, with a significant probability, it is not one-way.

Perhaps the confusion comes from a misunderstanding about what the definition of a one-way function is. The definition you quote at the beginning is not the definition of a one-way function. Rather, it's the definition of a hardcore bit.

The part you quoted appears to claim/imply that it is the definition of a one-way function with hardcore bit (which is not the same as the definition of a one-way function). That claim/implication is not correct. The precise statement is that this is the definition of a function with hardcore bit. This definition implies nothing about onewayness. So why did they call it the definition of a one-way function with hardcore bit? I don't know; you'd have to ask the author. But my guess is that this definition is normally only used with functions you already know to be one-way, so there's an implicit assumption that $f$ is already known to be one-way, and given such an $f$, the definition is describing what it means for $b$ to be hardcore for $f$.

You say "suppose $f$ isn't one-way, then this expectation will be noticeably different from 1/2". That actually doesn't follow. You can have a function $f$ that isn't one-way but does have a hardcore bit. Then the expectation will not be noticeably different from 1/2. E.g., consider the function $f$ given by $f(x)=0$: it's not one-way, but it does have a hardcore bit, and the expectation is exactly 1/2.

It sounds like you want to understand one-wayness. If so, hardcore bits are a distraction. You should be looking for the definition of a one-way function and trying to understand that, not looking at the definition of a hardcore bit.

• I never claimed that the expectation depends on $x$. I said the probability depends on $x$. I'm referring here to the $\mathbb{P}$ in the body of the expectation. Also I wasn't aware that there was a separate definition for one-way functions. So perhaps I should've written "suppose $b$ isn't a hard-core bit for $f$" instead. Nonetheless, I'm currently in the context of using one-way functions (and hard-core bits) to construct pseudorandom generators. So I think I should stick to this definition. – Sebastian Oberhoff Mar 15 '18 at 13:01
• Also when I say "Note that $A(f(x)) = b(x)$ is an event, not because $x$ is random, but because $A$ is a randomized algorithm" I'm trying to prevent people from having the same confusion as me here: math.stackexchange.com/questions/2689662/… – Sebastian Oberhoff Mar 15 '18 at 13:12
• @SebastianOberhoff, you're right. My fault. I read too quickly. I've done a major edit to my answer to remove all those incorrect parts. Can you take another read through my answer? Now hopefully it more directly addresses your confusion. – D.W. Mar 15 '18 at 16:37
• The proof that is introduced by the quoted segment later arrives at a contradiction by constructing a procedure $B$ for which $\mathbb{E}[\mathbb{P}(B(f(x))=b(x))] = 1/2 + \overline{o(k^{-c})}$ holds. (The left hand side is 1/2 plus something outside $o(k^{-c})$). So in expectation we can do a good job, whereas (2) claims we can always do a good job. – Sebastian Oberhoff Mar 16 '18 at 7:02
• Besides I'm not even sure how having a $1/\text{poly}(k)$ chance of success even qualifies as doing a good job. There are no obvious means of checking that you got the right answer for $b(x)$, so producing the right answer with such a probability seems useless. – Sebastian Oberhoff Mar 16 '18 at 7:02