Paper 2016/565

Bounded Indistinguishability and the Complexity of Recovering Secrets

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson

Abstract

Motivated by cryptographic applications, we study the notion of {\em bounded indistinguishability}, a natural relaxation of the well studied notion of bounded independence. We say that two distributions $\mu$ and $\nu$ over ${\mathrm{\Sigma }}^n$ are {\em $k$-wise indistinguishable} if their projections to any $k$ symbols are identical. We say that a function $f:{\mathrm{\Sigma }}^n\to \text{zo}$ is {\em $\text{e}$-fooled by $k$-wise indistinguishability} if $f$ cannot distinguish with advantage $$ between any two $$-wise indistinguishable distributions $$ and $$ over $$. We are interested in characterizing the class of functions that are fooled by $$-wise indistinguishability. While the case of $$-wise independence (corresponding to one of the distributions being uniform) is fairly well understood, the more general case remained unexplored. When $$, we observe that whether $$ is fooled is closely related to its approximate degree. For larger alphabets $$, we obtain several positive and negative results. Our results imply the first efficient secret sharing schemes with a high secrecy threshold in which the secret can be reconstructed in AC$$. More concretely, we show that for every $$ it is possible to share a secret among $$ parties so that any set of fewer than $$ parties can learn nothing about the secret, any set of at least $$ parties can reconstruct the secret, and where both the sharing and the reconstruction are done by constant-depth circuits of size $$. We present additional cryptographic applications of our results to low-complexity secret sharing, visual secret sharing, leakage-resilient cryptography, and protecting against ``selective failure'' attacks.

Note: Full version of paper appearing in Crypto 2016.