Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-093 | 1st July 2021 22:30

Bounded Indistinguishability for Simple Sources


Authors: Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan
Publication: 4th July 2021 05:37
Downloads: 114


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.

ISSN 1433-8092 | Imprint