How can I prove the following:

If $f$ is a one-way function, then it is an uninvertible function?


closed as unclear what you're asking by figlesquidge, Maeher, AFS, user6961, John Deters Jan 29 '14 at 5:51

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 10
    $\begingroup$ Can you update the question with your definition of one-way and uninvertible? To prove the statement you're given, you need to understand the essence of why the two definitions are different. $\endgroup$ – Reid Jan 28 '14 at 5:59

One-way in the context of cryptography is usually defined to mean that, given an element from the range of a function (or even a series of elements from the range), it is not possible in time polynomial in the input (or maybe output) size to identify the element(s) in the domain that yields the range element(s). This is purely a bound on computational complexity. I can absolutely identify every input for any deterministic encryption algorithm by simply exhaustively searching all possible inputs until the desired output is found. It's only that that will take time($O(2^n))$) for $n$-bit inputs.

Uninvertible is usually defined as a mathematical property of a function which says that an inverse for each element of the range is not guaranteed to exist, or at least to uniquely exist. For example, let $f(a,b)=a\wedge b$, and let $x$ be an output of $f$. What are the values of $a,b$ that produced it? They could be any of $(0,0), (0,1), (1,0)$ if $x=0$, so $f$ is not uniquely invertible.

My guess is that what you really want to show is something like this: Let $f$ be some computable function and let $x=f(a)$ be the output of $f$ at some unique $a\in dom(f)$. If $f$ is one-way (as defined above), then $a$ cannot be computed in time poly($|a|$) given only $x$.

This re-statement assumes definitions for what you mean by one-way and uninvertible. But with that assumption, the proof is simple--just apply the definitions. Intuitively, if you could compute $a$ from $x$ in polynomial time, then $f$ is not one-way by the definition. More formally, suppose there exists a deterministic, polynomial-time algorithm $A$ such that $A(x)=a$ for all $x\in dom(f)$ and $f(a)=x$. Then the pre-image of $x$ under $f$ can be computed in polynomial time, and so $f$ cannot be one-way. This is a contradiction, so $A$ cannot exist. qed.


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