# One-way functions and P=NP

This site contains various discussions of one-way functions and their relation to P versus NP.

Some of these discussions use a language $$L=\{(x',y) ~\mid~ x'\le x \text{ and } f(x)=y \}$$, where $$f:\Sigma^*\to\Sigma^*$$ is the one-way function and $$x'\le x$$ is the prefix relation. Now one central claim is that this language $$L$$ is contained in NP, since the word $$x$$ is a YES-certificate for $$(x',y)\in L$$.

I do not see why this claim is justified.
Why is the length of the certificate $$x$$ polynomially bounded in the length of $$(x',y)$$?

Couldn't it be possible that $$x$$ is exponentially long in $$y$$ and $$x'$$, but $$f(x)$$ is short and quickly computable from $$x$$?

• It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536. – Joshua Dec 17 '18 at 19:56

Yes, it could be that in the language you give, $$x$$ is exponentially long in $$(y,x')$$, and $$f$$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $$f(x)$$ needs not be computable in time polynomial in $$(y,x')$$).

However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $$P \neq NP$$. Intuitively, to fix this, modify your language as follows:

$$L=\{(1^n, x',y) ~\mid~ \exists x, |x| = n, x'\le x, \text{ and } f(x)=y \}$$,

where $$1^n$$ means a sequence of $$n$$ consecutive one, which exactly allows to fix the issue you point out (note that here $$x'\le x$$ means $$x'$$ is a prefix of $$x$$).

Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.

• Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$. – Alexis Dec 17 '18 at 15:04
• Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…). – Geoffroy Couteau Dec 17 '18 at 15:29
• With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly. – tylo Dec 18 '18 at 11:56