2026-07-23T07:14:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15622 2024-03-06T10:55:47Z ddc:004 open_access

Bounded Indistinguishability for Simple Sources Bogdanov, Andrej Dinesh, Krishnamoorthy Filmus, Yuval Ishai, Yuval Kaplan, Avi Srinivasan, Akshayaram Pseudorandomness bounded indistinguishability complexity of sampling constant-depth circuits secret sharing leakage-resilient cryptography A pair of sources X, Y over {0,1}ⁿ are k-indistinguishable if their projections to any k coordinates are identically distributed. Can some 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 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 X, Y, samplable by degree-O(log n) polynomial maps (over F₂) and by poly(n)-size decision trees, that are Ω(1)-distinguishable by OR. - There exists a function f such that all f(d, ε)-indistinguishable X, Y 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(log^{10}(1/ε)). - Extending (weaker versions of) the above negative results to AC^0 distinguishers would require settling a conjecture of Servedio and Viola (ECCC 2012). Concretely, if every pair of n^{0.9}-indistinguishable X, Y that are samplable by linear maps is ε-indistinguishable by AC^0 circuits, then the binary inner product function can have at most an ε-correlation with AC^0 ◦ ⊕ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrej Bogdanov and Krishnamoorthy Dinesh and Yuval Filmus and Yuval Ishai and Avi Kaplan and Akshayaram Srinivasan 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.26 urn:nbn:de:0030-drops-156223 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.26 eng https://creativecommons.org/licenses/by/4.0/legalcode