8
$\begingroup$

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

$\endgroup$
15
$\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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What if P != NP and one-way functions do not exist, as might occur if NP = coNP? $\endgroup$ – Philip White May 23 '15 at 1:47
  • 3
    $\begingroup$ @PhilipWhite we'd be somewhere between Heuristica and Pessiland then, I guess: cseweb.ucsd.edu/~russell/average.ps $\endgroup$ – Sasho Nikolov May 23 '15 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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '15 at 4:28
  • $\begingroup$ @RickyDemer: Whoops, I didn't mean to imply surjectivity. Fixed. $\endgroup$ – Joshua Grochow May 25 '15 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 '15 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$ – Sasho Nikolov May 25 '15 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$ – Joshua Grochow May 26 '15 at 16:48

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.