**Bounded Indistinguishability and the Complexity of Recovering Secrets**

*Andrej Bogdanov and Yuval Ishai and 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 $\Sigma^n$ are {\em $k$-wise indistinguishable} if their projections to any $k$ symbols are identical. We say that a function $f\colon \Sigma^n \to \zo$ is {\em $\e$-fooled by $k$-wise indistinguishability} if $f$ cannot distinguish with advantage $\e$ between any two $k$-wise indistinguishable distributions $\mu$ and $\nu$ over $\Sigma^n$.

We are interested in characterizing the class of functions that are fooled by $k$-wise indistinguishability. While the case of $k$-wise independence (corresponding to one of the distributions being uniform) is fairly well understood, the more general case remained unexplored.

When $\Sigma = \zo$, we observe that whether $f$ is fooled is closely related to its approximate degree. For larger alphabets $\Sigma$, 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$^0$. More concretely, we show that for every $0 < \sigma < \rho \leq 1$ it is possible to share a secret among $n$ parties so that any set of fewer than $\sigma n$ parties can learn nothing about the secret, any set of at least $\rho n$ parties can reconstruct the secret, and where both the sharing and the reconstruction are done by constant-depth circuits of size $\poly(n)$. 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.

**Category / Keywords: **Foundations of cryptography, secret sharing, visual cryptography, low-complexity cryptography, indistinguishability, leakage resilience cryptography

**Original Publication**** (in the same form): **IACR-Crypto-2016

**Date: **received 3 Jun 2016, last revised 6 Jun 2016

**Contact author: **yuvali at cs technion ac il

**Available format(s): **PDF | BibTeX Citation

**Note: **Full version of paper appearing in Crypto 2016.

**Version: **20190305:125121 (All versions of this report)

**Short URL: **ia.cr/2016/565

[ Cryptology ePrint archive ]