License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.26
URN: urn:nbn:de:0030-drops-156223
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15622/
Bogdanov, Andrej ;
Dinesh, Krishnamoorthy ;
Filmus, Yuval ;
Ishai, Yuval ;
Kaplan, Avi ;
Srinivasan, Akshayaram
Bounded Indistinguishability for Simple Sources
Abstract
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.
BibTeX - Entry
@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26,
author = {Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram},
title = {{Bounded Indistinguishability for Simple Sources}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {26:1--26:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15622},
URN = {urn:nbn:de:0030-drops-156223},
doi = {10.4230/LIPIcs.ITCS.2022.26},
annote = {Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography}
}
|
Keywords: |
|
Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
