1
$\begingroup$

I read a proof in my script: If $P = NP\implies $ there exists no OWF $f$. A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$

Their proof was a bit messy so I want to ask if the following technique (in general) can be used to proof similar problems:

Assume $P = NP$, and a OWF $f$ over $\{0, 1\}^n$ (We can transform any alphabet to $\{0, 1\}^n$). We have to show that $f^{-1}$ can be calculated in $PTIME$. Assume we are given $y$ and have to calculate $x$ so that $f(x) = y$.

$\exists NTM \space M $, that can check every possible String in $\{0, 1\}^n$ in $\mathcal{O}(n)$ time (binary tree). $M$ works like this:

For every $i=1,...,n$ it checks every string $s \in \{0, 1\}^n$ with $|s|=i$. So, for $i=2:f(00),f(01),f(10),f(11)$. Because $M$ is non-deterministic, it can traverse every layer of the binary tree simultaneously. If $f(s) = y \implies $ $M$ found the $x$ so that $f(x) = y$.

Therefore, $f^{-1}$ is in NP. If $P = NP$ $\implies$ $f^{-1}$ is in $P$ and there would not exist an OWF.

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to the site. Did you mean to ask $P=NP\rightarrow $ there doesn't exist a OWF? Since this is what the proof implies, rather than $P\neq NP\rightarrow $ there doesn't exist a OWF. $\endgroup$
    – nir shahar
    Commented Jul 14, 2021 at 13:40
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Jul 15, 2021 at 8:09
  • $\begingroup$ Thank you @D.W. for the reminder :) $\endgroup$
    – David
    Commented Jul 16, 2021 at 8:42

2 Answers 2

2
$\begingroup$

The core idea is good. You might want to elaborate more on how this process is done in detail:

Let us keep in mind that an OWF is a function $F$ that can be computed in $poly(n)$ time but $F^{-1}$ cannot be computed in polynomial time.

Assume that $P=NP$. Therefore, to prove that there is no OWF, we will show that no function $F$ can be a OWF. Notice that it is enough to find for any function $F$ computable in $poly(n)$ time a non-deterministic TM that computes $F^{-1}$ in $poly(n)$ time (since then we could convert this TM to be deterministic).

However, doing that is easy: Let $y$ be the input for that machine. We will non-deterministically guess an $x$, and we will verify that $y=F(x)$. Since we know that $F$ can be computed in polynomial time, then this entire verification process is polynomial as well. Hence, this algorithm is a non-deterministic polynomial algorithm computing $F^{-1}$. From what we said earlier, since we assumed $P=NP$, then $F$ cannot be a OWF, and hence we proved the claim.

$\endgroup$
1
  • $\begingroup$ Thank you for your straightforward answer! $\endgroup$
    – David
    Commented Jul 15, 2021 at 9:01
0
$\begingroup$

$f$ is a one way function if given $x, y = f(x)$ can be calculated in polynomial time in the size of $x$, but given $y$ knowing that $y = f(x)$, $x$ cannot be calculated in polynomial time in the size of $y$.

$NP$ is only about yes/no questions, but if we ignore that then the problem of finding $x$ is (kind of) in $NP$, because all we need to do is guess the right $x$ and verify in polynomial time that $y = f(x)$. However it is not in $P$, because to be in $P$, we would have to be able to find $x$ without any oracle or lucky guesses, and by the definition of "one-way function" we can't do that for one-way functions.

Now in practice we don't require OWF's to be non-polynomial, but just very hard to solve. We might find an $f$ where we can find $x$ from $g(x)$ in $n^{100}$ seconds, where $n$ is the size of $y$. That's "one-way" enough for all practical purposes; you can't even solve this for $n=2$. Such an "OWF" could still exist if $P=NP$.

$\endgroup$

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.