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 subseteq [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

9月25日（周二）14:00-15:00

Speaker

Tianren Liu is a fifth year student in MIT studying cryptography, advised by Prof Vinod Vaikuntanathanand. Before graduated school, he was studying in Yao class until 2014.

 
His research forces on information theoretic secure cryptography, including secret sharing and secure computation. He also studies the impossibility of basing cryptography on NP-hardness.

Venue

信息管理与工程学院  602会议室

上海财经大学

上海市杨浦区武东路100号