A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general.

We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular:

– There exist $\Omega(\sqrt{n})$-indistinguishable $\mathbf{X},\mathbf{Y}$, samplable by degree $O(\log n)$ polynomial maps (over $\mathbb{F}_2$) and by $\mathit{poly}(n)$-size decision trees, that are $\Omega(1)$-distinguishable by OR.

– There exists a function $f$ such that all $f(d, \epsilon)$-indistinguishable $\mathbf{X},\mathbf{Y}$ that are samplable by degree-$d$ polynomial maps are $\epsilon$-indistinguishable by OR for all sufficiently large $n$. Moreover, $f(1, \epsilon) = \lceil\log(1/\epsilon)\rceil + 1$ and $f(2, \epsilon) = O(\log^{10}(1/\epsilon))$.

– Extending (weaker versions of) the above negative results to $\mathit{AC^0}$ distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012).
Concretely, if every pair of $n^{0.9}$-indistinguishable $\mathbf{X},\mathbf{Y}$ that are samplable by linear maps is $\epsilon$-indistinguishable by $\mathit{AC^0}$ circuits, then the binary inner product function can have at most an $\epsilon$-correlation with $\mathit{AC^0}\circ\oplus$ circuits.

Finally, we motivate the question and our results by presenting applications of positive results to
low-complexity secret sharing and applications of negative results to leakage-resilient cryptography.

Minor edits.

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et al. (Crypto 2016) observe that this is not the case in general.

We initiate a systematic study of this question for natural classes of low-complexity sources, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers. In particular:

– There exist $\Omega(\sqrt{n})$-indistinguishable $\mathbf{X},\mathbf{Y}$, samplable by degree $O(\log n)$ polynomial maps (over $\mathbb{F}_2$) and by $\mathit{poly}(n)$-size decision trees, that are $\Omega(1)$-distinguishable by OR.

– There exists a function $f$ such that all $f(d, \epsilon)$-indistinguishable $\mathbf{X},\mathbf{Y}$ that are samplable by degree-$d$ polynomial maps are $\epsilon$-indistinguishable by OR for all sufficiently large $n$. Moreover, $f(1, \epsilon) = \lceil\log(1/\epsilon)\rceil + 1$ and $f(2, \epsilon) = O(\log^{10}(1/\epsilon))$.

– Extending (weaker versions of) the above negative results to $\mathit{AC^0}$ distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012).
Concretely, if every pair of $n^{0.9}$-indistinguishable $\mathbf{X},\mathbf{Y}$ that are samplable by linear maps is $\epsilon$-indistinguishable by $\mathit{AC^0}$ circuits, then the binary inner product function can have at most an $\epsilon$-correlation with $\mathit{AC^0}\circ\oplus$ circuits.