# Difficulty in proving the existence of one-way functions

By definition:

A polynomial-time computable function $$f:$$ $$\{$$0,1$$\}^*$$$$\{$$0,1$$\}^*$$ is a one-way function if for every probabilistic polynomial time Turing Machine $$PTM$$ there is a neglegibible function $$E$$ $$:\mathbb{N} → \mathbb{N}$$ $$\ s.t. \$$ $$Pr$$ $$x$$ $$∈$$ $$\{$$0,1$$\}^n$$ $$[PTM \ \ inverts \ \ f(x)] ≤ E(n)$$.

Now, reading the definition above, the existence of one-way functions seems like an easy bet, however it is considered a stronger assumption than $$P \neq NP$$. Apparently proving the existence of these functions would be more difficult than proving $$P = NP ?$$ And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

What steps would a mathematician or computer scientist take to prove that one-way functions exist? I believe that since proving its existence would also prove $$P \neq NP$$, this means that we cannot use the techniques that we know for sure does not work: Relativization, diagonalization, Natural Proof.

So, what form could such a proof take? Maybe something in second(+)-order logic?

• I'm not sure how this is a better question than asking what a $\mathsf{P} \neq \mathsf{NP}$ proof would look like. Perhaps the question is better poised as "what form could such a proof not take (in addition to relativization techniques, etc.)?" Jul 15, 2019 at 7:37
• This question should scrap all mention of P≠NP (which is separate question) and simply focus on why it's hard to prove one-way functions exist. Sep 16, 2023 at 16:55

Apparently proving the existence of these functions would be more difficult than proving $$P\not =NP$$? And I'd like to know the technical reasons for this, does it have something to do with the "for every" in the definition?

The answer is in your question itself:

I believe that since proving its existence would also prove $$P\not =NP$$

This is indeed the case. Somebody that proves the existence of one-way functions automatically also proves $$P\not = NP$$. On the other hand, it is conceivable that you could prove $$P\not = NP$$ without proving that one way functions exist. Thus, proving the existence of one-way functions is at least as hard as proving $$P\not = NP$$.

What steps would a mathematician or computer scientist take to prove that one-way functions exist?

Coming up with an extremely clever and creative idea that nobody came up with before.

• "The answer is in your question itself[:] 'I believe that since proving its existence would also prove P≠NP'" You're asked "Why is it difficult to prove the existence of one-way functions?" and you 'answer' "Because I assume P≠NP." Sep 16, 2023 at 16:53
• @Geremia No, that's not what my answer is. My "assumption" is that settling the P v.s. NP question is hard (since a lot of people have tried and nobody has managed). Now if you believe that settling P v.s. NP (either way) is hard, then proving that one-way functions exist must also be hard: if you managed to do so you'd also prove that P≠NP, but it is not impossible that P≠NP but no one-way functions exist. Therefore proving that one-way functions exist is a "strictly harder" task than proving that P≠NP. Sep 17, 2023 at 6:37