A secret-sharing scheme for a monotone Boolean (access) function F : {0, l}~n → {0,1} is a randomized algorithm that on input a secret, outputs n shares s_1,...,s_n such that for any (x_1,... ,x_n)∈ {0, l}~n, the collection of shares {s_1 : x_i - 1} determine the secret if F(x_1,... ,x_n) = 1 and reveal nothing about the secret otherwise. The best secret sharing schemes for general monotone functions have shares of size Θ(2~n). It has long been conjectured that one cannot do much better than 2~(Ω(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~(2n/2) monotone functions over {0,1}~n with sub-exponential share size 2~O(√n log (n).This unconditionally refutes the stronger conjecture that circuit size is, within polynomial factors, 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, l}~n with shares of size 2~O(√n long 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 → {0,1} with communication complexity 2~O(√n long n).
展开▼
