Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

All examples of one-way functions I have see till now are closely related to the assumption that $NP\neq P $ (or even weaker ones, such as $UP\neq P$), but why not considering the theorem $P\neq EXP$?

In particular, why not building functions that in one way are in the class $FP$ and the inverse function computable in $FEXP$ (the class of functions extending the class $EXP$)?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

If $P=NP$, then any one-way function can be inverted. Any one-way function can be inverted using non-deterministic polynomial time. Therefore, the assumption that $P\ne NP$ is necessary (but maybe not sufficient).

share|improve this answer
this is not complete answer ! you just said that we use the assumption that $NP\neq P$ ! but even if $P=NP$ this not immediately correct that we can easily invert one way functions , my question is asking why not use other classes of complexity to provide one way functions ? –  Fayez Abdlrazaq Deab Sep 3 '13 at 9:32
"even if $P=NP$ this not immediately correct that we can easily invert one way functions" - Yes it is. If $P=NP$, all one-way functions can be inverted in polynomial time. This is a simple theorem. (Remember, a one-way function must be computable in the forward direction in polynomial time. This means if you have a guess at the inverse, you can check whether your guess is correct in polynomial time. That in turn means that finding the inverse is a problem in $NP$: it's a problem whose solution can be verified in polytime, which is basically the definition of $NP$.) –  D.W. Sep 3 '13 at 18:12
this explanation is marvelous ... now I have better understanding of these things ... –  Fayez Abdlrazaq Deab Sep 4 '13 at 8:45

$UP \neq P$ is not a weaker assumption than $NP \neq P$. It is straightforward to show that if one-way functions exist then $NP \not\subseteq BPP$. For all functions $f$ in $FP$, $f^{-1} \in FEXP$ to the extent that $f^{-1}$ makes sense.

share|improve this answer
you suggest that we can't build function like I said ? then this not form any proof . happens that one of the basic functions we know the "one time pad" function : given a natural number ,$n$, output the two number that I've added that get this number . this function is one way because you can add numbers very quickly but the other side is not even computable ! then my question have enough sense . –  Fayez Abdlrazaq Deab Sep 3 '13 at 9:20
That function is not one-way. $\;$ –  Ricky Demer Sep 3 '13 at 9:39
why not ? all algorithms can just provide correct answer of small fraction of all possible inputs ? –  Fayez Abdlrazaq Deab Sep 3 '13 at 9:42
Because it's easy to find a correct answer on any input for which there is a correct answer. $\;$ –  Ricky Demer Sep 3 '13 at 9:43
Reread the definition. $\:$ $w$ is a correct answer if and only if $f(w) = f(x)$. $\:$ It would be sufficient to have $w=x$, but that is not necessary. $\:$ I don't understand the part of your previous comment that is after "one time pad". $\;\;\;$ –  Ricky Demer Sep 3 '13 at 9:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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