Paper 2020/664

The Share Size of Secret-Sharing Schemes for Almost All Access Structures and Graphs

Amos Beimel
Oriol Farràs
Abstract

The share size of general secret-sharing schemes is poorly understood. The gap between the best known upper bound on the total share size per party of $2^{0.59n}$ (Applebaum and Nir, CRYPTO 2021) and the best known lower bound of $\Omega(n/\log n)$ (Csirmaz, J. of Cryptology 1997) is huge (where $n$ is the number of parties in the scheme). To gain some understanding on this problem, we study the share size of secret-sharing schemes of almost all access structures, i.e., of almost all collections of authorized sets. This is motivated by the fact that in complexity, many times almost all objects are hardest (e.g., most Boolean functions require exponential size circuits). All previous constructions of secret-sharing schemes were for the worst access structures (i.e., all access structures) or for specific families of access structures. We prove upper bounds on the share size for almost all access structures. We combine results on almost all monotone Boolean functions (Korshunov, Probl. Kibern. 1981) and a construction of (Liu and Vaikuntanathan, STOC 2018) and conclude that almost all access structures have a secret-sharing scheme with share size $2^{\tilde{O}(\sqrt{n})}$. We also study graph secret-sharing schemes. In these schemes, the parties are vertices of a graph and a set can reconstruct the secret if and only if it contains an edge. Again, for this family there is a huge gap between the upper bounds - $O(n/\log n)$ (Erdös and Pyber, Discrete Mathematics 1997) - and the lower bounds - $\Omega(\log n)$ (van Dijk, Des. Codes Crypto. 1995). We show that for almost all graphs, the share size of each party is $n^{o(1)}$. This result is achieved by using robust 2-server conditional disclosure of secrets protocols, a new primitive introduced and constructed in (Applebaum et al., STOC 2020), and the fact that the size of the maximal independent set in a random graph is small. Finally, using robust conditional disclosure of secrets protocols, we improve the total share size for all very dense graphs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2020
Keywords
Secret sharingconditional disclosure of secrets protocolsgraph access structures
Contact author(s)
amos beimel @ gmail com
oriol farras @ urv cat
History
2023-01-31: revised
2020-06-03: received
See all versions
Short URL
https://ia.cr/2020/664
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/664,
      author = {Amos Beimel and Oriol Farràs},
      title = {The Share Size of Secret-Sharing Schemes for Almost All Access Structures and Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/664},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/664}},
      url = {https://eprint.iacr.org/2020/664}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.