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,\dots ,s_n$ such that for any $(x_1,\dots ,x_n)\in \{0,1{\}}^n$, the collection of shares $\{s_i:x_i=1\}$ determine the secret if $F(x_1,\dots ,x_n)=1$ and reveal nothing about the secret otherwise. The best secret sharing schemes for general monotone functions have shares of size $\mathrm{\Theta }(2^n)$. It has long been conjectured that one cannot do much better than $2^{\mathrm{\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 $$ monotone functions over $$ with sub-exponential share size $$. 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 $$ with shares of size $$. 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 $$ with communication complexity $$.