Welcome to the resource topic for
**2017/940**

**Title:**

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

**Authors:**
Amos Beimel, Oriol Farràs, Yuval Mintz, 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).

**ePrint:**
https://eprint.iacr.org/2017/940

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .