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$
$\endgroup$
4
-
$\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, 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.SoleiJun 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$– Daniel AponJun 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.SoleiJun 23, 2015 at 16:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
