ECCC-Report TR98-017https://eccc.weizmann.ac.il/report/1998/017Comments and Revisions published for TR98-017en-usMon, 30 Mar 1998 19:26:51 +0300
Paper TR98-017
| Computational Indistinguishability: A Sample Hierarchy. |
Oded Goldreich,
Madhu Sudan
https://eccc.weizmann.ac.il/report/1998/017
We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena cannot exist for non-uniform classes of
distinguishers, say, polynomial-size circuits).
It was also known that there exist pairs of ensembles which may be efficiently
distinguished based on {\em two}\/ samples but cannot be efficiently
distinguished based on a {\em single}\/ sample.
In contrast, it was not known whether the distinguishing power increases
when one moves from two samples to polynomially-many samples.
We show the existence of pairs of ensembles which may be efficiently
distinguished given $k+1$ samples but cannot be efficiently
distinguished given $k$ samples, where $k$ can be any function
bounded above by a polynomial in the security parameter.
In course of establishing the above result,
we prove several technical lemmas regarding polynomials and graphs.
We believe that these may be of independent interest.
Mon, 30 Mar 1998 19:26:51 +0300https://eccc.weizmann.ac.il/report/1998/017