7
$\begingroup$

I am not an expert in this field, but I have read that the existence of one-way functions implies $P \neq NP$. Since there seem to be so many different definitions of one-way-functions and I have not seen a proof I wanted to ask if someone knows where to read this, or knows the proof. Please if you give a proof, also give a precise definition of which version of "one-way-function" you use. The proof can of course be detailed, the detailed, the better! :) Thanks!

$\endgroup$
  • 5
    $\begingroup$ Suppose, for the sake of contradiction, that $P=NP$ and there is a one-way function $f$. You know $f$ is computed by a poly-size circuit. Given $y$, can you think of a way to find $x$ with $f(x)=y$? $\endgroup$ – Thomas Oct 2 '15 at 20:09
  • $\begingroup$ I guess the poly-size circuit problem is in NP, so since by assumption P=NP, we can solve the poly-size circuit problem in polynomial time and thus invert $f$ which contradicts the assumption that $f$ is one-way. But I didn't know of the connection of $f$ to the poly-size circuit problem. Do you have any reference for this? $\endgroup$ – orgesleka Oct 2 '15 at 20:15
  • $\begingroup$ Assuming $P=NP$, there is an algorithm that takes as input a circuit computing a function $f : \{0,1\}^n \to \{0,1\}$, outputs $x$ with $f(x)=1$ if such an $x$ exists, and runs in time polynomial in $n$ and the size of the circuit. $\endgroup$ – Thomas Oct 2 '15 at 21:42
  • $\begingroup$ Ok, but how does one construct an $NP$ complete problem given a one-way-function (Definition of Wikipedia)? $\endgroup$ – orgesleka Oct 3 '15 at 8:53
  • 1
    $\begingroup$ Checking whether a given circuit has a satisfying assignment is an NP-complete problem. $\endgroup$ – Thomas Oct 3 '15 at 15:05
11
$\begingroup$

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

$\endgroup$
  • 9
    $\begingroup$ it would be helpful to sketch out/ summarize some of the proof. $\endgroup$ – vzn Oct 5 '15 at 0:30
6
$\begingroup$

If P=NP, every polytime computable 1-1 function $f$ has a polytime computable inverse: $\{(x,y) \mid \exists z\ |yz| \leq poly(|x|) \land f(yz)=x \}$ is NP. We can find a $y$ such that $f(y)=x$ by starting with the empty string as$y$ and greedily adding the following bits using this NP oracle.

$\endgroup$
5
$\begingroup$

Let $f:\{0,1\}^* \rightarrow \{0,1\}^*$ be a OWF and define $L_f = \{(x,y)\in \{0,1\}^* \times \{0,1\}^*:$ there exists $z$ such that $f(xz)=y\}$. I construct the following non-deterministic Turing machine: $A((x,y)):$"Non-deterministically guess $z$. return ACCEPT if $f(xz)=y$ and REJECT otherwise" $A$ makes a single call to $f$ which is OWF and therefore runs in polynomial time. $A$ decides $L_f$ therefore $L_f \in NP$.

Assuming $P=NP$, there exists a deterministic polynomial time decider $A'$ such that $A'((x,y)) = ACCEPT \iff A((x,y)) = ACCEPT$. Using $A'$ I construct $f'$ which inverts $f$ in deterministic polynomial time. First, I define a helper function $h:(\{0,1\}^*,\{0,1\}^*) \rightarrow \{0,1\}^*$ the following way:

$h(x,y) = $ \begin{cases} h(x0,y),& \text{if } A'(x0, y) = ACCEPT\\ h(x1,y),& \text{if } A'(x1, y) = ACCEPT\\ x & \text{otherwise} \end{cases}

$h$ is a recursive function that tries to add a single bit $b$ to $x$ in every iteration. If $A'$ accepts $xb$, that means there exists some $z$ such that $f(xbz) = y$. In this case, $h$ recalls itself with $xb$. Once $|z| = 0$ I know parameter $x$ contains the preimage of $y$ and the DTM $A'$ would reject both $(x0,y)$ and $(x1,y)$. In this case $h$ returns $x$. $h$ runs in deterministic polynomial time in $|xz|$ since at every iteration $|x|$ grows by 1 on account of $|z|$. At every iteration $h$ calls $A'$ which runs in polynomial time, making the total runtime of $h$ polynomial.

Using $h$ I define the function $f':\{0,1\}^* \rightarrow \{0,1\}^*$ such that $f'(y) = $ "Initialize $x$ to be empty and return $h(x,y)$". $f'$ inverts $f$ in deterministic polynomial therefore $f$ is not OWF, reaching contradiction. In conclusion, if there exists a OWF, then $P \neq NP$.

$\endgroup$
  • $\begingroup$ If P=NP, any polytime computable 1-1 function has a polytime computable inverse. The proof is not even a paragraph: $\{(x,y) \mid \exists z\ |yz| \leq poly(|x|) \land f(yz)=x \}$ is NP. We can find a $y$ by starting at empty string and greedily adding the following bits using this NP oracle. $\endgroup$ – Kaveh Dec 10 '16 at 11:31
  • $\begingroup$ That's exactly what I did. $\endgroup$ – Ben Danon Dec 10 '16 at 12:45
  • 1
    $\begingroup$ It was already hinted under the question. Your answer is too long for this basic question imo. Anyone who has seen a reduction from search to decision should be able to fill out the rest. $\endgroup$ – Kaveh Dec 10 '16 at 13:59
  • 1
    $\begingroup$ Every point in my answer is a necessary logical step. $\endgroup$ – Ben Danon Dec 10 '16 at 14:24
  • 1
    $\begingroup$ Not on this site. Have you checked help center? If someone cannot fill in the gaps like these then probably they should ask the question on our sister site Computer Science in place of here. $\endgroup$ – Kaveh Dec 10 '16 at 15: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.