Paper 2017/940

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).

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