We consider the existence of pairs of probability ensembles which may be efficiently distinguished given k samples but cannot be efficiently distinguished given kk 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.
展开▼
机译:我们考虑了几对概率集合的存在,它们可以在给定k个样本的情况下有效区分,但不能在给定kk个样本的情况下有效区分。众所周知,在任何这种成对的集合中,都不可能两者都是可有效计算的(并且对于非均匀分类器,例如多项式大小的电路,这种现象不可能存在)。还已知存在成对的成对集合,这些成对集合可以基于{ em two} /样本而被有效地区分,但是不能基于{ em single} /样本而被有效地区分。相反,当一个样本从两个样本移动到多项式样本时,判别力是否会增加是未知的。我们显示了成对的合奏的存在,在给定k + 1个样本的情况下可以有效区分,但在给定k个样本的情况下不能有效地区分,其中k可以是安全性参数上由多项式限定的任何函数。在建立上述结果的过程中,我们证明了多项式和图的几个技术引理。我们认为,这些可能是独立利益。
展开▼