DESIGN OF PRACTICAL AND PROVABLY GOOD RANDOM NUMBER GENERATORS

We present a construction for a family of pseudo-random generators tha t are very fast in practice, yet possess provable statistical and cryp tographic unpredictability properties. Such generators are useful for simulations, randomized algorithms, and cryptography. Our starting poi nt is a slow but high quality generator whose use can be mostly confin ed to a preprocessing step. We give a method of stretching its outputs that yields a faster generator. The fast generator offers smooth memo ry-time-security trade-offs and also has many desired properties that are provable. The slow generator can be based on strong one-way permut ations or block ciphers. Our implementation based on the block cipher DES is faster than popular generators. (C) 1998 Academic Press.