Paper 2018/333
Breaking the CircuitSize Barrier in Secret Sharing
Tianren Liu and Vinod Vaikuntanathan
Abstract
We study secret sharing schemes for general (nonthreshold) 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 longstanding questions in informationtheoretic cryptography is to minimize the (total) size of the shares in a secretsharing 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^{no(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 secretsharing 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^{no(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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. 50th Annual ACM SIGACT Symposium on the Theory of Computing
 DOI
 10.1145/3188745.3188936
 Keywords
 secret sharing
 Contact author(s)
 liutr @ mit edu
 History
 20180411: received
 Short URL
 https://ia.cr/2018/333
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/333, author = {Tianren Liu and Vinod Vaikuntanathan}, title = {Breaking the CircuitSize Barrier in Secret Sharing}, howpublished = {Cryptology ePrint Archive, Paper 2018/333}, year = {2018}, doi = {10.1145/3188745.3188936}, note = {\url{https://eprint.iacr.org/2018/333}}, url = {https://eprint.iacr.org/2018/333} }