2
$\begingroup$

How can I prove the following:

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

$\endgroup$
  • 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
4
$\begingroup$

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.

$\endgroup$

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