Approximate Bounded Indistinguishability

Abstract

Two distributions over n-bit 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 read-once 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 degree-k 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 complex-analytic methods. As a secondary contribution, we derive new threshold weight lower bounds for bounded depth AND-OR formulas.