# Proving that a function is not a OWF (One-way-function)

I was trying to prove that a given function is not a one way function and I was not sure how to do it because maybe I had unclear what a one way function was (OWF).

The definition that I have for a OWF is the following:

Easy to compute for all inputs: for all PPT A (probabilistic polynomial time algorithms), A(x) = f(x) $\forall x$

But hard to invert:

$$Pr[B(1^k, f(x)) = x' \ s.t. \ f(x) = f(x')] < neg(k)$$

for all probabilistic polynomial time adversaries.

However, the part that I was unclear about is, if EVERY f(x) has to be hard to invert, or if its ok for it to be easy to invert say for only and only two values (say f(x) and f($\neg x$) ). I guess I was a little confused about the "invertibility" part of the definition. Is there a problem if its easy to invert for some inputs?

• The "Easy to compute" part is clearly wrong since for any function $f$ we can define a PPT algorithm $A$ that simply output $\lnot f(0)$ for all $x$. That is, a PPT algorithm that is not equal to $f(x)$ at least for $x = 0$. The right definition should say "for some PPT A" instead of "for all PPT A". Jul 5, 2017 at 7:10
To prove that a function is not a OWF, you can exhibit an inversion algorithm and show that your inversion algorithm succeeds in inverting the OWF with non-negligible probability. In other words, if we randomly choose $x$, compute $f(x)$, feed $f(x)$ to your inversion algorithm, and let $x'$ denote the output of your algorithm, then you need to show that $\Pr[f(x')=f(x)]$ is non-negligible. Thus, this is average-case hardness, averaging over all possible inputs to the OWF.
• @Pinocchio, yes, for a random $x$. Yes, my answer does not depend upon how $f$ is constructed; it applies regardless.