Paper 2017/940

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Amos Beimel, Oriol Farràs, Yuval Mintz, and Naty Peter

Abstract

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph $G=(V,E)$ if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in $E$ (i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes. A secret-sharing scheme is linear if the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. dense) graph with $n$ vertices and at most $n^{1+\beta}$ edges (resp. at least $\binom{n}{2} - n^{1+\beta}$ edges), for some $ 0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure in which the total size of the shares is $\tilde{O} (n^{1+\beta/2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is $\tilde{O} (n^{1/4+\beta/4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size $\Omega(n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every $0 \leq \beta < 1$ there exist a graph with at most $n^{1+\beta}$ edges and a graph with at least $\binom{n}{2}-n^{1+\beta}$ edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is $\Omega (n^{1+\beta/2})$. Finally, we show that for every $0 \leq \beta < 1$ there exist a graph with at most $n^{1+\beta}$ edges and a graph with at least $\binom{n}{2}-n^{1+\beta}$ edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is $\Omega (n^{1/4+\beta/4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

Note: We provided more general lower bounds. We added constructions of linear secret-sharing schemes for forbidden access structures with different trade-offs between the max share size and the total share size.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2017
Keywords
Secret-sharingshare sizemonotone span programconditional disclosure of secrets
Contact author(s)
naty @ post bgu ac il
oriol farras @ urv cat
amos beimel @ gmail com
History
2020-07-11: last of 4 revisions
2017-09-27: received
See all versions
Short URL
https://ia.cr/2017/940
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/940,
      author = {Amos Beimel and Oriol Farràs and Yuval Mintz and Naty Peter},
      title = {Linear Secret-Sharing Schemes for Forbidden Graph Access Structures},
      howpublished = {Cryptology ePrint Archive, Paper 2017/940},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/940}},
      url = {https://eprint.iacr.org/2017/940}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.