Bogdanov, Andrej ;
Williamson, Christopher
Approximate Bounded Indistinguishability
Abstract
Two distributions over nbit strings are (k,delta)wise indistinguishable if no statistical test that observes k of the n bits can tell the two distributions apart with advantage better than delta. Motivated by secret sharing and cryptographic leakage resilience, we study the existence of pairs of distributions that are (k, delta)wise indistinguishable, but can be distinguished by some function f of suitably low complexity. We prove bounds tight up to constants when f is the OR function, and tight up to logarithmic factors when f is a readonce uniform AND \circ OR formula, extending previous works that address the perfect indistinguishability case delta = 0.
We also give an elementary proof of the following result in approximation theory: If p is a univariate degreek polynomial such that p(x) <= 1 for all x <= 1 and p(1) = 1, then l (p) >= 2^{Omega(p'(1)/k)}, where lˆ (p) is the sum of the absolute values of p’s coefficients. A more general 1 statement was proved by Servedio, Tan, and Thaler (2012) using complexanalytic methods. As a secondary contribution, we derive new threshold weight lower bounds for bounded depth ANDOR formulas.
BibTeX  Entry
@InProceedings{bogdanov_et_al:LIPIcs:2017:7467,
author = {Andrej Bogdanov and Christopher Williamson},
title = {{Approximate Bounded Indistinguishability}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {53:153:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7467},
URN = {urn:nbn:de:0030drops74671},
doi = {10.4230/LIPIcs.ICALP.2017.53},
annote = {Keywords: pseudorandomness, polynomial approximation, secret sharing}
}
2017
Keywords: 

pseudorandomness, polynomial approximation, secret sharing 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 