Paper 2019/231

Secret-Sharing Schemes for General and Uniform Access Structures

Benny Applebaum
Amos Beimel
Oriol Farràs
Oded Nir
Naty Peter
Abstract

A secret-sharing 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 secret-sharing scheme whose shares are of size $2^{n-o(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 secret-sharing 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 secret-sharing 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 secret-sharing schemes for uniform access structures from them, and combines these schemes in order to obtain secret-sharing schemes for general access structures. Our second contribution in this paper is constructions of secret-sharing schemes for uniform access structures. We achieve the following results: a) A secret-sharing 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 secret-sharing 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 secret-sharing 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 ad-hoc 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 secret-sharing schemes for $k$-uniform access structures for a binary secret.

Note: Full version of the EUROCRYPT 2019 paper.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
DOI
10.1007/978-3-030-17659-4_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
2023-10-06: last of 2 revisions
2019-02-28: received
See all versions
Short URL
https://ia.cr/2019/231
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/231,
      author = {Benny Applebaum and Amos Beimel and Oriol Farràs and Oded Nir and Naty Peter},
      title = {Secret-Sharing Schemes for General and Uniform Access Structures},
      howpublished = {Cryptology ePrint Archive, Paper 2019/231},
      year = {2019},
      doi = {10.1007/978-3-030-17659-4_15},
      note = {\url{https://eprint.iacr.org/2019/231}},
      url = {https://eprint.iacr.org/2019/231}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.