1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – lamontap
    Commented Oct 3, 2023 at 20:08
  • $\begingroup$ @lamontap I edited the question, I hope it’s a bit more clear now :) $\endgroup$
    – Noel Arteche
    Commented Oct 3, 2023 at 21:11

1 Answer 1

Reset to default
2
$\begingroup$

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

Christopher M. Homan and Mayur Thakur, One-way permutations and self-witnessing languages.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! This is what I was looking for. $\endgroup$
    – Noel Arteche
    Commented Oct 3, 2023 at 23:23

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