TY - GEN
T1 - On linear secret sharing for connectivity in directed graphs
AU - Beimel, Amos
AU - Paskin, Anat
PY - 2008
Y1 - 2008
N2 - In this work we study linear secret sharing schemes for s-t connectivity in directed graphs. In such schemes the parties are edges of a complete directed graph, and a set of parties (i.e., edges) can reconstruct the secret if it contains a path from node s to node t. We prove that in every linear secret sharing scheme realizing the st-con function on a directed graph with n edges the total size of the shares is Ω(n 1.5). This should be contrasted with s-t connectivity in undirected graphs, where there is a scheme with total share size n. Our result is actually a lower bound on the size monotone span programs for st∈-∈con, where a monotone span program is a linear-algebraic model of computation equivalent to linear secret sharing schemes. Our results imply the best known separation between the power of monotone and non-monotone span programs. Finally, our results imply the same lower bounds for matching.
AB - In this work we study linear secret sharing schemes for s-t connectivity in directed graphs. In such schemes the parties are edges of a complete directed graph, and a set of parties (i.e., edges) can reconstruct the secret if it contains a path from node s to node t. We prove that in every linear secret sharing scheme realizing the st-con function on a directed graph with n edges the total size of the shares is Ω(n 1.5). This should be contrasted with s-t connectivity in undirected graphs, where there is a scheme with total share size n. Our result is actually a lower bound on the size monotone span programs for st∈-∈con, where a monotone span program is a linear-algebraic model of computation equivalent to linear secret sharing schemes. Our results imply the best known separation between the power of monotone and non-monotone span programs. Finally, our results imply the same lower bounds for matching.
UR - https://www.scopus.com/pages/publications/52149106245
U2 - 10.1007/978-3-540-85855-3_12
DO - 10.1007/978-3-540-85855-3_12
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:52149106245
SN - 3540858547
SN - 9783540858546
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 172
EP - 184
BT - Security and Cryptography for Networks - 6th International Conference, SCN 2008, Proceedings
T2 - 6th International Conference on Security and Cryptography for Networks, SCN 2008
Y2 - 10 September 2008 through 12 September 2008
ER -