# How to prove that a one way function is uninvertible?

Suppose we define the "hard to invert" part in the definition of one-way functions differently:

A function $\ f : \{0,1\}^* \to \{0,1\}^*$ is called uninvertible if it is easy to compute $f$ but there does not exist a PPT (polynomial time) algorithm $\ A$ such that, for every string $x$, on input $\ (1^k; f(x))$, $\ A$ outputs $x'$ such that $\ f(x) = f(x')$.

How to show that if $\ f$ is a one-way function, then it is an uninvertible function.

I know that if $\ f(a,b) = a\land b$, and let $x$ be an output of $\ f$. So there cannot be unique values of $a,b$ such that this is invertible. So basically this is uninvertible. I am not getting the connection between PPT algorithm and uninvertible function.

• Invertablity isn't about finding the orignal input, it's about finding any input matching the output. – CodesInChaos Aug 26 '17 at 7:50

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very efficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.
The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unique preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.
$f$ being not uninvertible does not imply it's invertible in this sense.