Welcome to the resource topic for 2018/333
Title:
Breaking the Circuit-Size Barrier in Secret Sharing
Authors: Tianren Liu, Vinod Vaikuntanathan
Abstract:We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for n parties is associated to a monotone function \mathsf F:\{0,1\}^n\to\{0,1\}. In such a scheme, a dealer distributes shares of a secret s among n parties. Any subset of parties T \subseteq [n] should be able to put together their shares and reconstruct the secret s if \mathsf F(T)=1, and should have no information about s if \mathsf F(T)=0. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions \mathsf F. There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general \mathsf F has shares of size 2^{n-o(n)}, but the best lower bound is \Omega(n^2/\log n). Indeed, the exponential share size is a direct result of the fact that in all known secret-sharing schemes, the share size grows with the size of a circuit (or formula, or monotone span program) for \mathsf F. Indeed, several researchers have suggested the existence of a {\em representation size barrier} which implies that the right answer is closer to the upper bound, namely, 2^{n-o(n)}. In this work, we overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size 2^{0.994n} and a linear secret sharing scheme for any access structure with shares of size 2^{0.999n}. As a contribution of independent interest, we also construct a secret sharing scheme with shares of size 2^{\tilde{O}(\sqrt{n})} for 2^{{n\choose n/2}} monotone access structures, out of a total of 2^{{n\choose n/2}\cdot (1+O(\log n/n))} of them. Our construction builds on recent works that construct better protocols for the conditional disclosure of secrets (CDS) problem.
ePrint: https://eprint.iacr.org/2018/333
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 .