首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Bounded Indistinguishability for Simple Source
  • 本地全文:下载
  • 作者:Andrej Bogdanov ; Krishnamoorthy Dinesh ; Yuval Filmus
  • 期刊名称: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.
国家哲学社会科学文献中心版权所有