next up previous
Next: Computational Sample Complexity Up: Sabbatical at MIT (1996-1998) Previous: Public-Key Cryptosystems from Lattice

Computational Indistinguishability - Algorithms vs. Circuits

It is shown that there exist pairs of distributions that are computationally indistinguishable by any probabilistic algorithms but are easily distinguishable by circuits. Furthermore, one distribution may be the uniform over strings of certain length, whereas the other may have a tiny support (of size that is any unbounded function of the string length).


Comments: Authored by O. Goldreich and B. Meyer. Appeared in



Oded Goldreich
2003-07-30