# Worst-case one-way permutations under P different from NP

This is probably obvious, but I cannot find it anywhere, since all textbooks define OWFs for average-case hardness.

Do we known if worst-case one-way permutations exist assuming $$\mathbf{P} \neq \mathbf{NP}$$? I don't require average-case hardness, it suffices that the function is hard to invert in the worst-case. That is, assuming $$\mathbf{P} \neq \mathbf{NP}$$, is there a family of permutations $$f_n : \{0,1\}^n \to \{ 0,1\}^n$$, such that $$f_n$$ can be computed by circuits of size polynomial in $$n$$ but there is no family of poly-size circuits that inverts $$f_n$$ on all of its outputs?. (I stated for circuits, but I’m happy with the uniform setting too). I’d also be happy if the output space is a bit larger than $$\{0,1\}^n$$ as long as each $$f_n$$ is injective.

• Can you be more precise with what you mean by worst case one-wayness? Is the worst case over the choice of function or over the choice of input? Oct 3, 2023 at 20:08
• @lamontap I edited the question, I hope it’s a bit more clear now :) Oct 3, 2023 at 21:11

The following paper shows that worst-case one-way permutations exist if and only if $$\textsf{P} \ne \textsf{UP} \cap \textsf{coUP}$$. A problem is in $$\textsf{UP}$$ if all yes-instances have exactly one witness, and all no-instances have no witnesses. $$\textsf{UP}$$ is a subset of $$\textsf{NP}$$.