Breaking the Circuit-Size Barrier in Secret Sharing
Tianren Liu and Vinod Vaikuntanathan
Abstract
We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for parties is associated to a monotone function . In such a scheme, a dealer distributes shares of a secret among parties. Any subset of parties should be able to put together their shares and reconstruct the secret if , and should have no information about if . 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 .
There is a large gap between lower and upper bounds for secret sharing. The best known scheme for general has shares of size , but the best lower bound is . 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 . 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, .
In this work, we overcome this barrier by constructing a secret sharing scheme for any access structure with shares of size and a linear secret sharing scheme for any access structure with shares of size . As a contribution of independent interest, we also construct a secret sharing scheme with shares of size for monotone access structures, out of a total of of them. Our construction builds on recent works that construct better protocols for the conditional disclosure of secrets (CDS) problem.
@misc{cryptoeprint:2018/333,
author = {Tianren Liu and Vinod Vaikuntanathan},
title = {Breaking the Circuit-Size Barrier in Secret Sharing},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/333},
year = {2018},
doi = {10.1145/3188745.3188936},
url = {https://eprint.iacr.org/2018/333}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.