Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Bounded Indistinguishability and the Complexity of Recovering Secrets

RSS-Feed




Revision #1
Authors: Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
Accepted on: 7th June 2016 05:33
Downloads: 204
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
Downloads: 692
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.



ISSN 1433-8092 | Imprint