Next: On the random-oracle methodology
Up: Back at Weizmann (1998-2003)
Previous: Bounds on 2-Query Codeword
We initiate a general investigation of pseudo-random
implementations of huge random objects, and apply it to areas
in which random objects occur naturally.
A pseudo-random implementation of such type T object must generate
objects of type T (which can not be distinguished from random),
rather than objects which can not be distinguished from
random type T objects (although they are not type T at all).
Comments:
Authored by O. Goldreich, S. Goldwasser and A. Nussboim. Appeared in
ECCC, TR03-045, 2003.
- Proceedings of 44th FOCS, 2003, to appear.
Oded Goldreich
2003-07-30