Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-182 | 7th June 2016 05:33

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

Revision #1
Authors: Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
Accepted on: 7th June 2016 05:33
Keywords:

Abstract:

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by bounded indistinguishability.

When $\Sigma = \{0, 1\}$, 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 $\mathrm{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 $\mathrm{AC}^0$ circuits of size $\mathrm{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.

Changes to previous version:

### Paper:

TR15-182 | 13th November 2015 10:34

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

TR15-182
Authors: Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
Publication: 13th November 2015 19:25
We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by bounded indistinguishability.
When $\Sigma = \{0, 1\}$, 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 $\mathrm{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 $\mathrm{AC}^0$ circuits of size $\mathrm{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.