Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

How can I prove the following:

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

share|improve this question

closed as unclear what you're asking by figlesquidge, Maeher, AFS, e-sushi, John Deters Jan 29 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  
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. –  Reid Jan 28 at 5:59

2 Answers 2

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.

share|improve this answer

Onto, meaning that the entire codomain is reachable. All of the values in the codomain are mapped to by some elements in the domain. This does not give any requirements about the number of elements that map to a particular element, only that at least one element maps to each element.

One-to-one, meaning that each element is mapped to by at most one element in the domain. This prevents collisions.

Since the requirement for onto restricts the number of elements that map to an element in the codomain to be $>= 1$, and the requirement for one-to-one restricts the number of elements to be $<= 1$, we must conclude that both of these requirements together fix the number of elements that each element maps to, to $1$.

Thus, each element in the codomain is mapped to by exactly $1$ element in the domain, hence each element is assigned a unique partner, and hence it is invertable.

To conclude and answer your question, a function being one-to-one is necessary but not sufficient for it to be invertable.

share|improve this answer
1  
One-way != one-to-one. If you update your answer to explain why this is relevant to a question on one-way functions I'll be very happy to remove the downvote - please reply to this comment [ie write a comment @figlesquidge: blah] when you do it though, because I can't keep checking in. –  figlesquidge Jan 28 at 17:24

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