TR98-017 Authors: Oded Goldreich, Madhu Sudan

Publication: 30th March 1998 19:26

Downloads: 1637

Keywords:

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.