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

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

• Isn't L being in UP the same as $f$ being injective? – Peter Shor May 2 '20 at 12:07
• Yes, it is. How I have written, when $L \in NP \setminus UP$ then $f$ cannot be injective, because there can exist at least one acceptable path in the NTM. But, maybe I want some idea about how to prove this way in more formally. – Peter Hofschatter May 2 '20 at 12:11
• You cannot say that $f$ is a one-way function. One-way functions have a definition, which is very far from what you wrote. – Yuval Filmus May 2 '20 at 12:53
• If we do not consider the condition to the inverse function $f^{-1}$, then we could say that it is a one-way function. I was inaccurate in the question, you're right. – Peter Hofschatter May 2 '20 at 13:00

## 1 Answer

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.