Properties and cryptographic applications of indistinguishable distributions

Ph.D. ; Two distributions over n-bit strings are (k, δ)-wise indistinguishable if no statistical test that observes k of the n bits can tell the two distributions apart with advantage better than δ. A secret sharing scheme is a protocol for sharing information to a set of n parties in such a way that little or nothing is leaked to unauthorized coalitions whereas authorized coalitions are able to reconstruct. Motivated by cryptographic applications to secret sharing schemes, we study properties of indistinguishable distributions and consider the existence of pairs of distributions that are (k, δ)-wise indistinguishable, but can be distinguished by some function f of suitably low complexity, typically in the circuit complexity class AC⁰. Such constructions immediately yield secret sharing schemes with secret reconstruction procedures in AC⁰, a characteristic not enjoyed by most existing schemes, including linear schemes. Extending previously known results for the OR function, we prove indistinguishability bounds tight up to logarithmic factors when f is a read-once uniform AND ◦ OR formula. As a secondary contribution, we derive a new threshold weight lower bound for bounded depth AND ◦ OR formulas. ; We also prove, in the case of symmetric distributions, that perfect (local) indistinguishability implies approximate (near global) indistinguishability. Specifically, we show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically (K,K³/²·exp(−Ω(k²/K)))-wise indistinguishable for all k