- Section 3.6 in Foundations of Cryptography. See extract.
- The original abstract, 1986.
- The final version [JACM, Vol. 33, No. 4, October 1986]. (Copyright by ACM.)

Pseudorandom generators allow to efficiently generate long pseudorandom sequences from short random seeds. Pseudorandom functions are even more powerful: they allow efficient direct access to a huge pseudorandom sequence (which is not even feasible to scan bit-by-bit). Put in other words, pseudorandom functions can replace truly random functions in any efficient application (e.g., most notably in cryptography).

The theory of pseudorandomness was extended to functions
by Goldreich, Goldwasser and Micali.
In particular, it was shown how to construct pseudorandom functions,
using an arbitrary pseudorandom (bit) generator.
This means that a black box,
which has only **k** secret bits of storage,
can implement a function from **k**-bit strings to **k**-bit strings
that cannot be distinguished from a random function by any
**poly(k)**-time observer which can ``query'' the function on
arguments of his choice.

Back to Oded Goldreich's homepage.