Paper Info
Title
Breaking the Circuit-Size Barrier in Secret Sharing.
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 F:{0,1}n→{0,1}. In such a scheme, a dealer distributes shares of a secret s among n parties. Any subset of parties T ⊆ [n] should be able to put together their shares and reconstruct the secret s if F(T)=1, and should have no information about s if 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 F. There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general F has shares of size 2n−o(n), but the best lower bound is Ω(n2/logn). 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 F. Indeed, several researchers have suggested the existence of a representation size barrier which implies that the right answer is closer to the upper bound, namely, 2n−o(n). In this work, we overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size 20.994n and a linear secret sharing scheme for any access structure with shares of size 20.999n. As a contribution of independent interest, we also construct a secret sharing scheme with shares of size 2Õ(√n) for 2nn/2 monotone access structures, out of a total of 2nn/2· (1+O(logn/n)) of them. Our construction builds on recent works that construct better protocols for the conditional disclosure of secrets (CDS) problem.
Year
DOI
Venue
2018
10.1145/3188745.3188936
STOC '18: Symposium on Theory of Computing Los Angeles CA USA June, 2018
Keywords
DocType
Volume
Secret Sharing,Information-Theoretic Cryptography
Conference
2018
ISSN
ISBN
Citations 
0737-8017
978-1-4503-5559-9
2
PageRank 
References 
Authors
0.37
7
2
Name
Order
Citations
PageRank
Tianren Liu1204.08
Vinod Vaikuntanathan25353200.79