How to prove that a one way function is uninvertible?

Question

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.

Answer 1

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.

Concretely: cryptographers hope/assume that a cryptographic hash function is uninvertible (this is why we store hashes of passwords). Also, that RSA is one-way: an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is uninvertible is clear from the definitions (write down your definition of one-way function: it should be immediate; if not, edit your question adding that definition).