Paper 2016/565
Bounded Indistinguishability and the Complexity of Recovering Secrets
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and 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 constantdepth circuits of size $\poly(n)$. We present additional cryptographic applications of our results to lowcomplexity secret sharing, visual secret sharing, leakageresilient cryptography, and protecting against ``selective failure'' attacks.
Note: Full version of paper appearing in Crypto 2016.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in CRYPTO 2016
 Keywords
 Foundations of cryptographysecret sharingvisual cryptographylowcomplexity cryptographyindistinguishabilityleakage resilience cryptography
 Contact author(s)
 yuvali @ cs technion ac il
 History
 20160607: revised
 20160603: received
 See all versions
 Short URL
 https://ia.cr/2016/565
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/565, author = {Andrej Bogdanov and Yuval Ishai and Emanuele Viola and Christopher Williamson}, title = {Bounded Indistinguishability and the Complexity of Recovering Secrets}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/565}, year = {2016}, url = {https://eprint.iacr.org/2016/565} }