next up previous
Next: Pseudo-random functions Up: A Whirlwind Tour of Previous: Secret sharing

Pseudorandom number generators


Definition A cryptographically secure pseudorandom bit generator is an efficient algorithm that will expand a random n-bit seed to a longer sequence that is computationally indistinguishable from a truly random sequence.


Theorem [Levin] A one-way function can be used to construct a cryptographically secure pseudo-random bit generator.



Kevin McCurley
1/23/1998