0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What about $g = f$? No adversary can always invert f... $\endgroup$ – Christian Matt Mar 5 '17 at 0:14
  • $\begingroup$ @ChristianMatt sorry I forgot to mention $g$ must not be a weak OWF. $\endgroup$ – qweruiop Mar 5 '17 at 0:19
  • $\begingroup$ 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. $\endgroup$ – Christian Matt Mar 5 '17 at 0:55
  • $\begingroup$ @ChristianMatt Do you have any idea... $\endgroup$ – qweruiop Mar 5 '17 at 3:06
2
$\begingroup$

In order to answer this question, you first really need to define what a worst-case OWF is. In particular, is it possible to efficiently sample a hard instance? I assume not, because this would be very hard to formalize and I'm not sure it makes sense. If not, then there is an easy answer:

  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$.
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – qweruiop Mar 5 '17 at 22:32

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.