Cryptography, Statistics and Pseudo-Randomness (Part I)

In the classical approach to pseudo-random number generators, a generator is considered to perform well if its output sequences pass a battery of statistical tests that has become standard. In recent years, it has turned out that this approach is not satisfactory. Many generators have turned out to seriously bias the outcome of some simulation experiments in which they were put to use. From a theoretical point of view, the classical approach does not at all explain in what way a completely deterministic algorithm can be said to simulate randomness. Much less known is that cryptographers, who have a need for pseudo-random numbers of very high quality, have developed a theory that actually explains why a pseudo-random number generator can simulate randomness. Our aim in this two-part paper is to make this theory more accessible for mathematical statisticians and probabilists. 1 Introduction. The classical approach to simulating randomness by purely deterministic means has proved to be effective in many applications where randomness is needed. However, as computers ge