Next: Quantifying Knowledge Complexity
Up: The Technion Period (1986-94)
Previous: On the Composition of
The non-triviality of the notion of computational
indistinguishability, for sampleable distributions,
is shown to be equivalent to the existence of pseudorandom generators.
That is, it is shown how to transform two sampleable distributions
that are computationally indistinguishable
but statistically far apart, into a pseudorandom generator.
Comments:
Authored by O. Goldreich. Appeared in
- IPL, Vol. 34, pp. 277-281, May 1990.
Oded Goldreich
2003-07-30