עמוס ביימל

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.