7
$\begingroup$

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.

Improve this question
$\endgroup$
11

2 Answers 2

Reset to default
14
$\begingroup$

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$).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice answer. Would it make any difference if the randomness of PRNG defined as "unpredictable to any subexponential-time bounded adversary"? $\endgroup$
    – Mohammad Al-Turkistany
    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$
    – Joe Fitzsimons
    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$
    – Joe Fitzsimons
    Nov 10, 2010 at 10:10
10
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.