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.

  • 3
    $\begingroup$ Invertablity isn't about finding the orignal input, it's about finding any input matching the output. $\endgroup$ 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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