Cryptology ePrint Archive: Report 2017/1062

Towards Breaking the Exponential Barrier for General Secret Sharing

Tianren Liu and Vinod Vaikuntanathan and 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)}$.

Category / Keywords: secret sharing

Date: received 31 Oct 2017, last revised 21 Feb 2018

Contact author: liutr at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20180222:044903 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]