Secret Sharing and CDS (Tianren Liu)

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}^nto{0,1}. In such a scheme, a dealer distributes shares of a secret s among n parties. Any subset of parties T subsete q [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 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 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)}.

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 double exponential different monotone access structures.

Our secret sharing schemes build on our new protocol for conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. For genearl predicates where the input size is n for both parties, the best protocols prior to our work required communication complexity O(2^{n/2}).

We present the first protocol with 2^{O(sqrt(nlog n))} communication complexity. To obtain these results, we draw upon techniques for non-linear reconstruction developed in the context of information-theoretic private information retrieval (PIR).

Based on joint works with Vinod Vaikuntanathanand and Hoeteck Wee.

Time

Speaker

Room