Welcome to the resource topic for 2016/565
Title:
Bounded Indistinguishability and the Complexity of Recovering Secrets
Authors: 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.
ePrint: https://eprint.iacr.org/2016/565
Talk: https://www.youtube.com/watch?v=WeGs0Oi-6Jw
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .