Paper 2017/1062
Towards Breaking the Exponential Barrier for General Secret Sharing
Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee
Abstract
A secretsharing scheme for a monotone Boolean (access) function $F: \{0,1\}^n \to \{0,1\}$ is a randomized algorithm that on input a secret, outputs $n$ shares $s_1,\ldots,s_n$ such that for any $(x_1,\ldots,x_n) \in \{0,1\}^n$, the collection of shares $ \{ s_i : x_i = 1 \}$ determine the secret if $F(x_1,\ldots,x_n)=1$ and reveal nothing about the secret otherwise. The best secret sharing schemes for general monotone functions have shares of size $\Theta(2^n)$. It has long been conjectured that one cannot do much better than $2^{\Omega(n)}$ share size, and indeed, such a lower bound is known for the restricted class of linear secretsharing schemes. In this work, we *refute* two natural strengthenings of the above conjecture:  First, we present secretsharing schemes for a family of $2^{2^{n/2}}$ monotone functions over $\{0,1\}^n$ with subexponential share size $2^{O(\sqrt{n} \log n)}$. This *unconditionally* refutes the stronger conjecture that circuit size is a lower bound on the share size.  Second, we disprove the analogous conjecture for nonmonotone functions. Namely, we present nonmonotone secretsharing schemes for *every* access function over $\{0,1\}^n$ with shares of size $2^{O(\sqrt n \log n)}$. Our construction draws upon a rich interplay amongst old and new problems in informationtheoretic cryptography: from secretsharing, to multiparty computation, to private information retrieval. Along the way, we also construct the first multiparty conditional disclosure of secrets (CDS) protocols for general functions $F:\{0,1\}^n \rightarrow \{0,1\}$ with communication complexity $2^{O(\sqrt n \log n)}$.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 secret sharing
 Contact author(s)
 liutr @ mit edu
 History
 20180222: revised
 20171109: received
 See all versions
 Short URL
 https://ia.cr/2017/1062
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/1062, author = {Tianren Liu and Vinod Vaikuntanathan and Hoeteck Wee}, title = {Towards Breaking the Exponential Barrier for General Secret Sharing}, howpublished = {Cryptology ePrint Archive, Paper 2017/1062}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/1062}}, url = {https://eprint.iacr.org/2017/1062} }