IV.4 Perfect Pseudorandom Generators
The complete chapter as PDF file.
As we saw the essential cryptologic criterion for pseudorandom generators is unpredictability. In the 1980s cryptographers, guided by an analogy with asymmetric cryptography, found a way of modelling this property in terms of complexity theory: Prediction should boil down to a known »hard« algorithmic problem such as factoring integers or discrete logarithm. This idea established a new quality standard for pseudorandom generators, much stronger than statistical tests, but eventually building on unproven mathematical hypotheses. Thus the situation with respect to the security of pseudorandom generators is comparable to asymmetric encryption.
As an interesting twist it soon turned out that in a certain sense unpredictability is a universal property: For an unpredictable sequence there is no efficient algorithm at all that distinguishes it from a true random sequence, a seemingly much stronger requirement (YAO's theorem). This universality justifies the denomination »perfect« for the corresponding pseudorandom generators. In particular there is no efficient statistical test that is able to distinguish the output of a perfect pseudorandom generator from a true random sequence. Thus, on the theoretical side, we have a very appropriate model for pseudorandom generators that are absolutely strong from a statistical viewpoint, and invulnerable from a cryptological viewpoint. In other words:
Looking back at Section 3.6 we might stumble over the apparent contradiction with the general »rule«: »If a sequence has a short description (as the BBS sequence obviously has!), then it can't be random and even has a short description by a linear feedback shift register.« In particular this would yield an efficient algorithm that distinguishes it from a random sequence. However as already stated in 3.6 this rule leaves a small loophole—small small in relative terms but maybe wide enough in absolute terms. The notion of pseudorandomness tries to slip through this loophole, see the figure (where the size of the areas is by far not to scale):
In the literature we find many tests for randomness: