Cryptology ePrint Archive: Report 2016/565

Bounded Indistinguishability and the Complexity of Recovering Secrets

Andrej Bogdanov; Yuval Ishai; Emanuele Viola; 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: 20160607:034344 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]