9
$\begingroup$

Is there a conditional impossibility result or the question is completely open?

$\endgroup$

2 Answers 2

16
$\begingroup$

We cannot hope to prove a general impossibility result since if one-way functions exist (and we believe they do), then in particular it follows that the statement "If $P \ne NP$ then one-way functions exist" is true.

However, we can prove that certain proof techniques are too weak to prove that statement. In particular, the following paper of Akavia, Goldreich, Goldwasser and Moshkovitz proves that this statement cannot be proved by certain black-box reductions (conditioned on plausible assumptions):

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html

$\endgroup$
2
  • 1
    $\begingroup$ What if P != NP and one-way functions do not exist, as might occur if NP = coNP? $\endgroup$
    – user1338
    May 23, 2015 at 1:47
  • 3
    $\begingroup$ @PhilipWhite we'd be somewhere between Heuristica and Pessiland then, I guess: cseweb.ucsd.edu/~russell/average.ps $\endgroup$ May 23, 2015 at 6:46
10
$\begingroup$

If you mean the cryptographic kind of one-way function (i.e. average-case hard to invert), then Or Meir's answer is great. But for the slightly easier notion of worst-case one-way function - that is, an injective function $f$ that is computable in polynomial time, but where there is no deterministic polynomial-time algorithm $g$ such that $f(g(y)) = y$ for all $y$ in the image of $f$ and $g(y)=0$ otherwise - there is a more precise answer. Namely, worst-case one-way functions exist if and only if $\mathsf{P} \neq \mathsf{UP}$.

So for worst-case one-way functions, your question essentially boils down to the relationship between $\mathsf{UP}$ and $\mathsf{NP}$. This relationship is essentially wide open, and there are oracles in both directions. A few relationships for related questions are known - namely, Valiant-Vazirani ($\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$) and Hemaspaandra-Naik-Ogihara-Selman ($\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$ implies $\mathsf{PH}$ collapses) - but I'm not aware of any direct, unconditional relationship that deals with $\mathsf{NP}$ and $\mathsf{UP}$ precisely.

$\endgroup$
6
  • $\begingroup$ That's an ... odd definition for worst-case onewayness. $\:$ (In particular, it implies surjectivity.) $\hspace{.38 in}$ I would've expected it to mirror the cryptographic definition more closely. $\hspace{1.63 in}$ $\endgroup$
    – user6973
    May 25, 2015 at 4:28
  • $\begingroup$ @RickyDemer: Whoops, I didn't mean to imply surjectivity. Fixed. $\endgroup$ May 25, 2015 at 15:05
  • $\begingroup$ How is $\operatorname{UP}$ involved? $\:$ (Consider the function given by sending pairs [SAT_instance,satisfying_assignment] to their encoded SAT_instance, and everything else to something that's not a SAT instance.) $\;\;\;\;$ $\endgroup$
    – user6973
    May 25, 2015 at 20:26
  • 1
    $\begingroup$ After looking at sciencedirect.com/science/article/pii/0304397585900854, the definition for a worst case one way function seems to be: 1) $f$ is an injection, 2) $x$ and $f(x)$ are polynomially related in size, 3) $f(x)$ is polytime computable, 4) $f^{-1}(y)$ is not polytime computable for all $y$ in the range. $\endgroup$ May 25, 2015 at 22:10
  • 1
    $\begingroup$ @RickyDemer: When $f$ is injective, the range of $f$ - i.e. $\{ x : (\exists y)[f(y)=x]\}$ - is a language in $\mathsf{UP}$. $\endgroup$ May 26, 2015 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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