ECCC-Report TR15-182https://eccc.weizmann.ac.il/report/2015/182Comments and Revisions published for TR15-182en-usTue, 07 Jun 2016 05:33:59 +0300
Revision 1
| Bounded Indistinguishability and the Complexity of Recovering Secrets |
Andrej Bogdanov,
Yuval Ishai,
Emanuele Viola,
Christopher Williamson
https://eccc.weizmann.ac.il/report/2015/182#revision1We 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.
Tue, 07 Jun 2016 05:33:59 +0300https://eccc.weizmann.ac.il/report/2015/182#revision1
Paper TR15-182
| Bounded Indistinguishability and the Complexity of Recovering Secrets |
Andrej Bogdanov,
Yuval Ishai,
Emanuele Viola,
Christopher Williamson
https://eccc.weizmann.ac.il/report/2015/182We 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.
Fri, 13 Nov 2015 19:25:31 +0200https://eccc.weizmann.ac.il/report/2015/182