### 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 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.

Note: Full version of paper appearing in Crypto 2016.

Available format(s)
Publication info
Keywords
Foundations of cryptographysecret sharingvisual cryptographylow-complexity cryptographyindistinguishabilityleakage resilience cryptography
Contact author(s)
yuvali @ cs technion ac il
History
2016-06-07: revised
See all versions
Short URL
https://ia.cr/2016/565

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},
note = {\url{https://eprint.iacr.org/2016/565}},
url = {https://eprint.iacr.org/2016/565}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.