I am interested in what conditions are necessary and sufficient to define a cryptographically secure pseudo-random number generator (CSPRNG).
Wikipedia lists two defining characteristics:
- It satisfies the next-bit test.
- It withstands 'state compromise extensions' - part of all of the state being compromised does not allow for reconstruction of the prior stream of random numbers.
I understand that condition 1 is equivalent to saying there does not exist a polynomial-time algorithm which can distinguish the output stream from random (with success probability 1/2 + $\epsilon$), due to Yao (1982). I cannot, however, find any formal justification for the second criteria, which Wikipedia surmises as 'they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.' Does anyone have a reliable source for this?
Moreover, is this condition even sensible? If you consider something like RC4 (okay, not the best example of a CSPRNG I know), if you know the whole state at any point then it is possible to step the PRGA forward or backwards completely deterministically and independent of knowledge of the key, right? So, this means that RC4 does not satisfy Wikipedia's second condition for being a CSPRNG?