How to construct pseudorandom functions

Webpage for a paper by Oded Goldreich, Shafi Goldwasser and Silvio Micali


Material avialable on-line


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.