Next: Finding the Shortest Move-Sequence
Up: The Post-Doctoral Period (1983-86)
Previous: The Post-Doctoral Period (1983-86)
This work extends the theory of pseudorandomness to functions.
A collection of functions is called pseudorandom if it is
infeasible to distinguish the case one is given oracle access
to a function chosen uniformly in the collection from the case
one is given oracle access to a truely random function.
It is shown how to construct collections of pseudorandom
functions from any pseudorandom generator.
Comments:
Authored by O. Goldreich, S. Goldwasser and S. Micali. Appeared in
- Proc. of the 25th FOCS, 1984,
pages 464-479.
- Jour. of the ACM, Vol. 33,
No. 4, Oct. 1986, pp. 792-807.
Oded Goldreich
2003-07-30