期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A pair of sources XY over 01n are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some AC0 function distinguish between two such sources when k is big, say k=n01? Braverman's theorem (Commun. ACM 2011) implies a negative answer when 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 (n) -indistinguishable XY , samplable by degree O(logn) polynomial maps (over F2) and by poly(n)-size decision trees, that are (1)-distinguishable by OR. – There exists a function f such that all f(d) -indistinguishable XY that are samplable by degree-d polynomial maps are -indistinguishable by OR for all sufficiently large n. Moreover, f(1)=log(1)+1 and f(2)=O(log10(1)) . – Extending (weaker versions of) the above negative results to AC0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n09-indistinguishable XY that are samplable by linear maps is -indistinguishable by AC0 circuits, then the binary inner product function can have at most an -correlation with AC0 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.
