One-way function is not injective when it is in NP

Question

Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \rvert ^ k$. Thus, we can say that the function $f$ is one-way function.

We have language $L = \{ w \; | \; \exists z \in \Sigma^*, w = f(z)\}$. The question is, how to prove that $f$ is not injective if $L \in NP \setminus UP$, where $UP$ is the class of unambiguous TM.

It is clear, that if $L \in NP \setminus UP$ then exists NTM which decides this language and may exist at least one acceptable path for $w \in L$.

Answer 1

Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.

Since $L$ is always in $\mathsf{NP}$ (using the very same machine), the contrapositive is exactly the statement you're after.