We present a construction for a family of pseudo-random generators that are very fast in practice, yet possess provable statistical and cryptographic unpredictability properties. Such generators are useful for simulations, randomized algorithms, and cryptography.

Our starting point is a slow but high quality generator whose use can be mostly confined to a preprocessing step. We give a method of stretching its outputs that yields a faster generator. The fast generator offers smooth memory–time–security trade-offs and also has many desired properties that are provable. The slow generator can be based on strong one-way permutations or block ciphers. Our implementation based on the block cipher DES is faster than popular generators.