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 Jun 21 '15 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.Soleimani Jun 22 '15 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$ – Daniel Apon Jun 23 '15 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.Soleimani Jun 23 '15 at 16:43

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, privacy policy and cookie policy

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