Design of Practical and Provably Good Random Number Generators

✍ Scribed by Aiello, William (author);Rajagopalan, S. Raj (author);Venkatesan, Ramarathnam (author)

• Publisher: Academic Press
• Year: 1998
• Tongue: English
• Weight: 286 KB
• Volume: 29
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1998.0952

✦ Synopsis

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.