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?

  • $\begingroup$ This is probably just me not understanding the notation, but represents $f^{-1}$ all possible values if somebody does try to reverse the function? $\endgroup$
    – Maarten Bodewes
    Commented Jun 21, 2015 at 17:12
  • $\begingroup$ Yeah, actually A is an advetsary who tries to find a pre-image for y (where y=f(x)) $\endgroup$
    – A.Solei
    Commented Jun 22, 2015 at 11:06
  • 1
    $\begingroup$ 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/… $\endgroup$ Commented Jun 23, 2015 at 4:24
  • $\begingroup$ 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? $\endgroup$
    – A.Solei
    Commented Jun 23, 2015 at 16:43

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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