Paper 2017/940
Linear SecretSharing Schemes for Forbidden Graph Access Structures
Amos Beimel, Oriol Farràs, Yuval Mintz, and Naty Peter
Abstract
A secretsharing 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. Secretsharing 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 secretsharing schemes. A secretsharing 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 secretsharing 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 secretsharing 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 secretsharing 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 tradeoffs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secretsharing 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 secretsharing 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 secretsharing scheme realizing these forbidden graph access structures is $\Omega (n^{1/4+\beta/4})$. This shows that our constructions are optimal (up to polylogarithmic factors).
Note: We provided more general lower bounds. We added constructions of linear secretsharing schemes for forbidden access structures with different tradeoffs between the max share size and the total share size.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in TCC 2017
 Keywords
 Secretsharingshare sizemonotone span programconditional disclosure of secrets
 Contact author(s)

naty @ post bgu ac il
oriol farras @ urv cat
amos beimel @ gmail com  History
 20200711: last of 4 revisions
 20170927: received
 See all versions
 Short URL
 https://ia.cr/2017/940
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/940, author = {Amos Beimel and Oriol Farràs and Yuval Mintz and Naty Peter}, title = {Linear SecretSharing 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} }