Paper 2017/1062

Towards Breaking the Exponential Barrier for General Secret Sharing

Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee

Abstract

A secret-sharing 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 secret-sharing schemes. In this work, we *refute* two natural strengthenings of the above conjecture: -- First, we present secret-sharing schemes for a family of $2^{2^{n/2}}$ monotone functions over $\{0,1\}^n$ with sub-exponential 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 non-monotone functions. Namely, we present non-monotone secret-sharing 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 information-theoretic cryptography: from secret-sharing, to multi-party computation, to private information retrieval. Along the way, we also construct the first multi-party 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)}$.