# Worst case one way function

the worst-case one way function is defined as follows $$\forall A \exists x : pr(A(f(x))\in f^{-1}(f(x)))\neq 1$$ can you give any example of such function?

• This is probably just me not understanding the notation, but represents $f^{-1}$ all possible values if somebody does try to reverse the function? Jun 21, 2015 at 17:12
• Yeah, actually A is an advetsary who tries to find a pre-image for y (where y=f(x)) Jun 22, 2015 at 11:06
• The more usual notion of an (average-case) one-way function is, naturally, also a worst-case one-way function. See e.g. en.wikipedia.org/wiki/… Jun 23, 2015 at 4:24
• Thanks but I mean a function which is worst-case one way but not weak or strong(average-case) one way. do you have any idea about it? Jun 23, 2015 at 16:43

## 1 Answer

Worst-case one-way functions exist if and only if P ≠ NP, therefore, if I were you, I would not expect to get a definitive answer to your question any time soon :).

On the other hand, if you are willing to assume that P ≠ NP, then it is not hard to construct such a function (that is actually exactly a half of the proof of the theorem I stated in the previous paragraph).