**Linear Secret-Sharing Schemes for Forbidden Graph Access Structures**

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

**Abstract: **A secret-sharing scheme realizes the forbidden graph access structure determined by a graph $G=(V,E)$ if a pair of vertices can reconstruct the secret if and only if it is an edge in $G$. Secret-sharing schemes for forbidden graph access structures of bipartite graphs are equivalent to conditional disclosure of secrets protocols, a primitive that is used to construct attributed-based encryption schemes.

We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes. A secret-sharing scheme is linear if the reconstruction of the secret from the shares is a linear mapping. In many applications of secret-sharing, it is required that the scheme will be linear. 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 graph with $n$ vertices and at most $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})$. We provide an additional construction showing that every dense graph with $n$ vertices and at least $\binom{n}{2} - n^{1+\beta}$ edges can be realized by a linear secret-sharing scheme with the same total share size. Furthermore, for the above graphs we construct a linear secret-sharing scheme realizing their forbidden graph access structure in which the size of the share of each party is $\tilde{O} (n^{1/4+\beta/4})$.

We prove matching lower bounds on the share size of linear secret-sharing schemes realizing forbidden graph access structures. We prove that for most forbidden graph access structures, the total share size of every linear secret-sharing scheme realizing these access structures is $\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 these 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).

**Category / Keywords: **foundations / Secret-sharing, share size, monotone span program, conditional disclosure of secrets

**Original Publication**** (in the same form): **IACR-TCC-2017

**Date: **received 25 Sep 2017, last revised 7 Nov 2017

**Contact author: **amos beimel at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **Added constructions of linear secret-sharing schemes for forbidden access structures of sparse and dense graphs with small share size for each party.

**Version: **20171107:112955 (All versions of this report)

**Short URL: **ia.cr/2017/940

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]