Paper 2019/231
SecretSharing Schemes for General and Uniform Access Structures
Abstract
A secretsharing scheme allows some authorized sets of parties to reconstruct a secret; the collection of authorized sets is called the access structure. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secretsharing scheme whose shares are of size $2^{no(n)}$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $O(2^{0.994n})$. Our first contribution is improving the exponent of secret sharing down to $0.892$. For the special case of linear secretsharing schemes, we get an exponent of $0.942$ (compared to $0.999$ of Liu and Vaikuntanathan). Motivated by the construction of Liu and Vaikuntanathan, we study secretsharing schemes for uniform access structures. An access structure is $k$uniform if all sets of size larger than $k$ are authorized, all sets of size smaller than $k$ are unauthorized, and each set of size $k$ can be either authorized or unauthorized. The construction of Liu and Vaikuntanathan starts from protocols for conditional disclosure of secrets, constructs secretsharing schemes for uniform access structures from them, and combines these schemes in order to obtain secretsharing schemes for general access structures. Our second contribution in this paper is constructions of secretsharing schemes for uniform access structures. We achieve the following results: a) A secretsharing scheme for $k$uniform access structures for large secrets in which the share size is $O(k^2)$ times the size of the secret. b) A linear secretsharing scheme for $k$uniform access structures for a binary secret in which the share size is $\tilde{O}(2^{h(k/n)n/2})$ (where $h$ is the binary entropy function). By counting arguments, this construction is optimal (up to polynomial factors). c) A secretsharing scheme for $k$uniform access structures for a binary secret in which the share size is $kn\cdot2^{\tilde{O}(\sqrt{k \log n})}$. Our third contribution is a construction of adhoc PSM protocols, i.e., PSM protocols in which only a subset of the parties will compute a function on their inputs. This result is based on ideas we used in the construction of secretsharing schemes for $k$uniform access structures for a binary secret.
Note: Full version of the EUROCRYPT 2019 paper.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in EUROCRYPT 2019
 DOI
 10.1007/9783030176594_15
 Keywords
 secret sharingconditional disclosure of secrets protocolsprivate simultaneous messages protocols
 Contact author(s)

benny applebaum @ gmail com
amos beimel @ gmail com
oriol farras @ urv cat
odednir123 @ gmail com
natypeter @ mail tau ac il  History
 20231006: last of 2 revisions
 20190228: received
 See all versions
 Short URL
 https://ia.cr/2019/231
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/231, author = {Benny Applebaum and Amos Beimel and Oriol Farràs and Oded Nir and Naty Peter}, title = {SecretSharing Schemes for General and Uniform Access Structures}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/231}, year = {2019}, doi = {10.1007/9783030176594_15}, url = {https://eprint.iacr.org/2019/231} }