According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove that P!=NP. If it is considered impossible to prove mathematically that some bit sequence is random then it should be mathematically impossible to prove P!=NP, right? Are these two problems really equivalent? If they are then why all the hoopla over P vs NP, you can never prove it either way according to these definitions.
-
2$\begingroup$ @Paul, Could you please provide a link to the cited article? $\endgroup$– Mohammad Al-TurkistanyNov 10, 2010 at 8:39
-
$\begingroup$ @turkistany: I added the link. $\endgroup$– Sadeq DoustiNov 10, 2010 at 14:20
-
$\begingroup$ Thank you all for the replies,adding links and editing. You guys are too fast for me! $\endgroup$– Paul JohnsonNov 10, 2010 at 18:49
-
$\begingroup$ Voting to close as off-topic since this seems be a speculative attempt on $P$ vs $NP$ problem. See the later question posted by OP: cstheory.stackexchange.com/questions/3043/… $\endgroup$– KavehNov 16, 2010 at 9:19
-
$\begingroup$ Please see the meta-discussion: Is it ok to ask about the correctness of preprints on crank-friendly topics? $\endgroup$– KavehNov 16, 2010 at 11:24
2 Answers
There is a bit of an issue with your question. You are using the words unpredictable and secure interchangeably, which would seem to imply that you mean "unpredictable to a polynomial-time bounded adversary". This is not at all the same thing as being truly unpredictable, since clearly there is a function (in this case the PRNG) which generates them. So this is not related to any issue with proving that the sequence is 'truly' random in some sense. Rather, what you really need is that given the prior output of the PRNG it is computationally hard to predict the next number.
This formulation is clearly related to P vs NP since clearly calculating a sequence of $m$ pseudo-random numbers using the generator is in FP (the functional version of P) when the key $k$ to the PRNG is known. However given a set of $m$ sequential pseudo-random numbers outputted by the device, the problem of finding $k$ is clearly in FNP (the functional version of NP).
Thus proving that it is computationally easy to generate the pseudo random numbers but computationally hard to infer the key from a sample of the output of the PRNG would imply that $FP \neq FNP$ (and hence $P\neq NP$).
-
$\begingroup$ Nice answer. Would it make any difference if the randomness of PRNG defined as "unpredictable to any subexponential-time bounded adversary"? $\endgroup$ Nov 10, 2010 at 8:49
-
1$\begingroup$ @turkistany: Yes, since there are functions which are not believed to be in P but for which sub-exponential time algorithms are known, which could be used as the basis of the PRNG. For example, factoring, which has an algorithm which takes only $O(\exp(c n^{\frac{1}{3}}(\log n)^\frac{2}{3}))$. $\endgroup$ Nov 10, 2010 at 9:12
-
1$\begingroup$ Also, it seems to me that a sub-exponential time attacker may in fact be even more powerful than NP, since they can potentially use more than polynomial space. $\endgroup$ Nov 10, 2010 at 10:10
Every cryptographically-secure pseudo-random bit generator $G$ is a one-way function; since given the output $y$ of $G(\cdot)$ on some input (seed) $s$, it is computationally infeasible to obtain $s$ from $y$. (Otherwise, the generator is not cryptographically-secure). So we have:
cryptographically-secure pseudo-random bit generator exists $\Rightarrow$ one-way functions exist.
The existence of one-way functions is a stronger assumption than $\rm{P}\ne\rm{NP}$. That is:
one-way functions exist $\Rightarrow$ $\rm{P}\ne\rm{NP}$.
(For more info on this, see the Status of Impagliazzo's Worlds.)
Edit:
Impagliazzo, Levin, and Luby showed that the reverse holds under non-uniform assumptions; that is:
one-way functions exist $\Rightarrow$ cryptographically-secure pseudo-random bit generator exists.
(here, the security is with reference to non-uniform adversaries.)
Håstad generalized this to uniform adversaries.
Joining forces, Håstad, Impagliazzo, Levin, and Luby showed that:
cryptographically-secure pseudo-random bit generator exists if and only if one-way functions exist.