4
$\begingroup$

We know that If there exists a one-way function, then P ≠ NP. Why can we not conclude that if P ≠ NP, then there exists a one-way function? Is there a polynomial time computable function that is hard to invert in the worst case and isn't one-way?

$\endgroup$
2
$\begingroup$

Why can we not conclude that if P ≠ NP, then there exists a one-way function?

Because so far no one has been able to prove this statement, see here.

The statement "if one-way functions exist, then $P \neq NP$" is an implication, which just goes one way. If we build the contrapositive, we get "if $P = NP$, then one-way functions don't exist".

On the list of logical fallacies, we can find:

Those are (more or less) common errors regarding logic, and only the contrapositive does not change the actual meaning of the statement. Both inversion and conversion alone do not preserve the meaning - and thus are invalid if you want to prove a statement.

Is there a polynomial time computable function that is hard to invert in the worst case and isn't one-way

Any NP-complete search problem gives you a candidate for that. That is exactly the difference between search problems in the class NP and one-way functions: The former are defined with regard to the worst-case and the later are defined for the average-case. This is also why NP-complete problems are less interesting in cryptography, where it can be not enough if only the worst-case of a problem is hard.

$\endgroup$
  • $\begingroup$ "Any NP-complete search problem gives you a candidate for that." Could you please provide a reference for that? $\endgroup$ – Occams_Trimmer Mar 31 '17 at 12:01
  • $\begingroup$ @Occams_Trimmer It is just a different point of view of the very basic definition of NP. Consider the formula in the NP problem as function, e.g. in SAT that is just a boolean function over the input variables. The NP search problem is basically the search for a preimage to the output $True$, and the decision problem asks if $True$ has a preimage. However, this function is not one-way: It is really easy to find a preimage to the output $False$ - in oneway functions that must also be difficult. $\endgroup$ – tylo Mar 31 '17 at 12:33
  • $\begingroup$ Doesn't this apply to any Boolean function, one-way or not (because the input has to be chosen uniformly at random from the domain as per the definition of a OWF)? I have a feeling I am missing something. $\endgroup$ – Occams_Trimmer Mar 31 '17 at 19:43
  • $\begingroup$ @Occams_Trimmer Well, yes that fits the part about not being a OWF. No function can be a OWF if its output length is independent of the input length, because then it's not negligible. However, any boolean function isn't necessarily hard to invert. It doesn't even have to be hard to invert in the average case. If the problem is in NP and not P, that just means the worst case is hard to invert (in the sense that we don't have a poly time algorithm). $\endgroup$ – tylo Apr 3 '17 at 11:59

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.