Rigorous practical pseudorandom generators It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem.
I am curious if someone developed kind of &quot;practical&quot; PRGs, which are weaker than PRGs in terms of computational indistinguishably to uniform random number generators.
I know of some statistical tests for randomness, but is there any rigorous theory on the subject?
This is a repost from MO, and I intend to remove the original question.
It is worth mentioning that there is a connection in complexity theory often called &quot;Hardness v Pseudorandomness&quot; that makes this question somewhat difficult.
It may not be surprising that given a strong enough PRG, one can derandomize certain randomized algorithms, i.e. trying to prove $P = BPP$ can be done by giving a provably strong enough pseudorandom generator.
What is perhaps surprising is that this is intimately connected to the existence of hard problems in $NP$.
Specifically, if there is a problem in $NP$ that requires exponentially sized circuits, I believe it implies that $P = BPP$ via the construction of an explicit pseudorandom generator.
Moreover, some form of the reverse holds --- being able to derandomize $P$ (via the construction of a provably good PRG of good enough parameters) leads to circuit lower bounds, which is a notoriously hard subject.
Keywords for this are things like &quot;Nisan-Wigderson PRG&quot;, or you can look at these notes for some pointers.
I think (but am fuzzy on the details) that one can generalize the above to other circuit classes as well, i.e. the existence of explicit provably secure PRGs against some circuit class is intimately related to circuit lower bounds against some related circuit class.
As in general most circuit lower bounds we can prove are against fairly restricted models of computation, I would expect that the literature on &quot;rigorous PRGs&quot; is restricted to PRGs that are secure against relatively weak forms of computation.
I don't know a great place that summarizes this all --- I do not myself work in the area, but heard about it from someone who does. Perhaps their thesis would be a good reference, but I'll admit that I have not personally read it.