Welcome to the resource topic for 2017/1062
Title:
Towards Breaking the Exponential Barrier for General Secret Sharing
Authors: Tianren Liu, Vinod Vaikuntanathan, 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)}.
ePrint: https://eprint.iacr.org/2017/1062
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .