# worst-case OWF from weak OWF

A function $f$ is a worst-case OWF if there is no adversary $\mathcal{A}$ such that $$\forall x,Pr[y=f(x): f(\mathcal{A}(y))=y]=1$$

A weak OWF is a function that the probability of inverting it is bounded by some $1-\frac{1}{q(n)}$ for some polynomial function $q(n)$. The question is suppose $f$ is a weak OWF, can we define a function $g$ that is a worst-case OWF but not a weak OWF?

My idea is to make $g$ easy to invert for (exponentially) most inputs. This make $g$ "weaker than" any weak OWF. For example, consider $$g(x) = \left\{\begin{array}{ll}0 & x < 2^{|x|}-1 \\ f(x) & \text{otherwise} \end{array}\right.$$

Clearly $g$ is weaker than any weak OWF. But how can I show that no adversary can always invert $g$ then?

• What about $g = f$? No adversary can always invert f... – Christian Matt Mar 5 '17 at 0:14
• @ChristianMatt sorry I forgot to mention $g$ must not be a weak OWF. – qweruiop Mar 5 '17 at 0:19
• The $g$ you propose does not work: If an adversary can always invert $g$, we can only conclude that $f$ can be inverted for $x$ with $x \geq 2^{\lvert x \rvert}-1$, which happens with small probability for random $x$. Hence, there is no contradiction to $f$ being a weak OWF. – Christian Matt Mar 5 '17 at 0:55
• @ChristianMatt Do you have any idea... – qweruiop Mar 5 '17 at 3:06

1. If there exists a weak OWF then $P \neq NP$
2. If $P \neq NP$ then let $L\in NP\setminus P$ and let $R_L$ be its associated polynomial-time verifiable relation (i.e., $(x,y)\in R_L$ if and only if $x\in L$).
3. By the definition of a "worst-case" OWF, take a machine that samples $(x,y)\in R_L$ and outputs $x$.
4. The function would be defined to be $f(y)=x$.
• That's a good general construction. But I'm sort of asking for a concrete construction based on $f(x)$ (a given weak OWF). Also, the definition of worst-case OWF is now in the body of the question. Thanks! – qweruiop Mar 5 '17 at 22:32