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 ©(n1.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.

1 Introduction

Secret sharing schemes, introduced by [11,35,26], are a method in which a dealer

holding a secret can distribute shares to parties in a network such that only pre-

de¬ned authorized sets of parties can reconstruct the secret from their shares.

These schemes, whose original motivation was secure storage, have found nu-

merous applications as a building box in complex cryptographic schemes, e.g.,

Byzantine agreement [32], secure multiparty computations [8,16,17], threshold

cryptography [20], access control [30], and attribute based encryption [25]. In

most applications it is important that the scheme is linear, that is, the shares

are a linear combination of the secret and some random elements. Linear secret

sharing schemes are equivalent to monotone span programs, a computational

model introduced by Karchmer and Wigderson [28].

In this work we study linear secret sharing schemes for a natural function: the

parties are edges of a complete directed graph, and a set of parties (i.e., edges)

is authorized 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 ©(n1.5 ). Studying linear secret shar-

ing for this function has both a cryptographic motivation and a computational

complexity motivation. We ¬rst discuss the cryptographic motivation. Benaloh

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 172“184, 2008.

c Springer-Verlag Berlin Heidelberg 2008

On Linear Secret Sharing for Connectivity in Directed Graphs 173

and Rudich [10] (see also [4,28]) showed that there exists a simple and very e¬-

cient linear secret sharing scheme for the analogous function where the graph is

undirected. This scheme was used in [30] to design a protocol for reliable access

control. The obvious open problem is if this scheme can be generalized to deal

with directed graphs. The computational complexity motivation is separating the

power of monotone and non-monotone span programs. Our results imply that

over in¬nite ¬elds and large ¬nite ¬elds non-monotone span programs are more

e¬cient than monotone span programs by a multiplicative factor of ©(n0.5 ).

This is the best separation known to-date.

1.1 Previous Results

In this section we will give a short background on secret sharing schemes, lin-

ear secret sharing schemes, monotone span programs, and the equivalence of

the latter two notions. Finally, we will discuss some known results on the s-t

connectivity function.

Secret-sharing schemes were ¬rst introduced by Blakley [11] and Shamir [35]

for the threshold case, that is, for the case where the subsets that can reconstruct

the secret are all the sets whose cardinality is at least a certain threshold. Secret-

sharing schemes for general access structures were introduced by Ito, Saito, and

Nishizeki [26]. More e¬cient schemes were presented in, e.g., [9,36,14,28,37,22].

Even with the more e¬cient schemes, the size of the shares for general access

structures with n parties is 2O(n) , where the secret is an -bit string. Lower

bounds for secret sharing schemes were proved in [29,9,15,13,21,18,19,12,31].

The best lower bound was proved by Csirmaz [18], proving that, for every n,

there is an access structure with n parties such that sharing an -bit secrets

requires shares of length ©( n/ log n). Still there is an exponential gap between

the lower-bounds and the upper-bounds.

Span programs and monotone span programs, introduced by Karchmer and

Wigderson [28], are linear-algebraic models of computation. More speci¬cally,

a monotone span program is presented as a matrix over some ¬eld, with rows

labeled by variables. The span program accepts an input if the rows whose

variables are satis¬ed by the input span a ¬xed nonzero vector. The size of a

span program is its number of rows. A detailed de¬nition is given in Section 2.

Lower bounds for monotone span programs have been studied in several papers.

Beimel, G´l, and Paterson [6] provided a technique for proving lower bounds for

a

monotone span programs and proved a lower bound of O(n2.5 ) for a function

with n variables. Babai, G´l, and Wigderson [2], using the technique of [6],

a

proved the ¬rst super-polynomial lower bound “ they prove an n©(log n/ log log n)

lower bound for the size of monotone span programs for the clique problem.

G´l [23] gave a characterization of span program size and improved the lower

a

bound for the clique function to n©(log n) . Proving exponential lower bounds for

an explicit function is an open problem (it is known that such lower bound holds

for most functions [34]). G´l and Pudl´k [24] have shown limitations of current

a a

techniques for proving lower bounds for monotone span programs. Beimel and

Weinreb [7] showed a separating of the power of monotone span programs over

174 A. Beimel and A. Paskin

di¬erent ¬elds, for example, they showed that there are functions that have

small monotone span program over the ¬eld GF(2), however, they require super

polynomial monotone span programs over ¬elds whose characteristic is not 2.

In most applications of secret sharing schemes it is important that the scheme

is linear, that is, the shares are a linear combination of the secret and some

random elements. Linearity implies that if we sum shares distributed for two

secrets, then we get shares of the sum of the secrets. This property is useful,

for example, when designing secure multi-party protocols [8,16,17]. Karchmer

and Wigderson [28] showed that monotone span programs imply linear secret

sharing schemes (this result was implicitly proved also by Brickell [14]). More

precisely, if there is a monotone span of size s computing a function f over a

¬eld F then there is a secret sharing scheme realizing f such that the domain

of secrets is F and the total number of bits of the shares is s log |F|. In fact,

monotone span programs and linear secret sharing schemes are equivalent [3].

Thus, proving lower bounds for monotone span programs implies the same lower

bounds for linear secret sharing schemes.

In this work we prove lower bounds for the st-con function. This function is

widely studied in complexity both for directed and undirected graphs. For ex-

ample, st-con in directed graphs is NL-complete, while Reingold [33] has proved

that st-con in undirected graphs is in deterministic log-space. Another exam-

ple where undirected st-con is easier than directed st-con was given by Ajtai

and Fagin [1]; they showed that while undirected st-con is de¬nable in monadic

second order logic, the directed case is not. We continue this line of research

by proving that for monotone span programs undirected st-con is easier than

directed st-con, although the gap we can prove is much smaller.

The circuit complexity of st-con has been studied as well. The directed (and

undirected) st-con function has a polynomial-size monotone circuit of depth

O(log n); this circuit has unbounded fan-in. This implies a monotone formula for

st-con of size nO(log n) and, using the construction of Benaloh and Leichter [9],

there is a secret sharing scheme realizing the st-con function in which the size of

the shares is nO(log n) . Karchmer and Wigderson [27] have proved that for mono-

tone formulae this is optimal “ every monotone formula computing undirected

(and, hence, directed) st-con function has size n©(log n) .

1.2 Our Results

In this work we prove that a monotone span program computing the st-con

function on a directed graph with n edges has size ©(n1.5 ). We supply two proofs

of this lower bound. The ¬rst proof uses the characterization of span program

size given by G´l [23]; this proof only holds for ¬nite ¬elds. The second proof

a

uses the condition of Beimel, G´l, and Paterson [6]; this proof holds for every

a

¬eld. As monotone span program are equivalent to linear secret sharing schemes,

our result implies that in every linear secret sharing scheme realizing the st-con

function in directed graphs, the total size of the shares is ©(n1.5 ).

Our lower bound has a few additional implications. First, it shows that, for

monotone span programs and linear secret sharing, undirected st-con is easier

On Linear Secret Sharing for Connectivity in Directed Graphs 175

than directed st-con. This is true since there is a monotone span program real-

izing undirected st-con whose size is n [10,28] (see Example 1 below).

Furthermore, our lower bound supplies the best known separation between

the power of monotone and non-monotone span programs. Beimel and G´l [5] a

proved that over in¬nite ¬elds and large ¬nite ¬elds the directed st-con function

on graphs with n edges has a non-monotone span program of size O(n). Thus,

our result shows a separation of multiplicative factor of ©(n0.5 ) between mono-

tone and non monotone span programs for directed st-con. Separations between

monotone and non-monotone models of computation is an important question