S(u, v). We refer to such entries (u, v) as “singletons”.

Observation 2. If |S(u, v)| is even, then Re (u, v) = 0 for some e ∈ S(u, v).

Su

L1 L2 L3 L4

s t

Tu

Fig. 1. An illustration of a path and a cut for which |S(u, v)| is even. The vertices in

Su are black and the vertices in Tu are white. The edges in S(u, v) are the edge between

L1 and L2 and the edge between L3 and L4 .

Lemma 1. Let c = 1/4. For d = 4 there are at least c|U ||V | pairs (u, v) such

that |S(u, v)| is even.5

Proof. From the de¬nition of U , V , and (2) in Theorem 3, it follows that S(u, v)

is precisely the set of edges in v that belong to Su — Tu (where the partition

Su ∪ Tu speci¬es the maxterm u). Fix some cut u ∈ U . For a path v the size of

S(u, v) is even if the path has an even number of edges going from Su to Tu . For

d = 4 this is true if the vertex in L2 is in Tu and the vertex in L3 is in Su , that

3

For an edge e = (s, x) or e = (x, t), the matrix Fe = 0 (by the de¬nition of the

maxterms). We, therefore, ignore such matrices).

4

This is true if x ∈ Lj for 2 ¤ j ¤ d ’ 1; the number of rows for x ∈ L1 or x ∈ Ld’1

w ¡d’2

= |U |/2.

is 0.5 w/2

5

For d = 5, the constant c is 0.5 and for any su¬ciently large d, this constant ap-

proaches 1/2.

On Linear Secret Sharing for Connectivity in Directed Graphs 179

is, the edges in S(u, v) are the edge between L1 and L2 and the edge between

L3 and L4 . See Fig. 1 for a description. Since half of the vertices of L2 are in Tu

and half of the vertices of L3 are in Su , for a quarter of the paths v ∈ V , the

size of S(u, v) is even.

We now move to our two main lemmas.

c

Lemma 2. There exist at least cw2 edges e such that Re contains at least a d

fraction of zeros, where c is the constant from Lemma 1.

Proof. We construct a set of edges as required, proceeding in iterations. By

Lemma 1, for all (u, v) the set

B = {(u, v) : |S(u, v)| is even}

must satisfy Re (u, v) = 0 for some edge e ∈ S(u, v). That is, we need to “cover”

the set B by edges in this sense, where e covers (u, v) ∈ B if Re (u, v) = 0.

Denote by Bi the set of entries uncovered at the beginning of iteration i. In

particular, B1 = B. By Lemma 1, |B1 | = c|U ||V | for some constant c. We start

an iteration i if |Bi | ≥ c|U ||V |/2. Since there are at most w2 (d ’ 1) ’ i ¤

c|U ||V |/2

w2 d edges to choose from, at least one of them should cover at least w2 d

uncovered entries (by the pigeon hole principle). We pick any of those e™s and

add it to the list. Note that the rectangle Re has at most |U |/2·|V |/w2 entries6 ,

thus a fraction of at least c/d of the entries of Re are 0. Each selected edge e

covers at most |U ||V |/2w2 uncovered entries (the number of entries in Re ).

Since we halt only when at least c|U ||V |/2 pairs in B have been covered, at

least cw2 iterations are needed.

To complete the proof, it remains to show that every rectangle Re with “many”

zeros, as in Lemma 2, has high degree.

Lemma 3. Let Re , for e = (x, y), be a rectangle with a fraction of at least c/d

zero entries. Then rankGF(2) (Re ) = ©(n0.5 ).

Proof. In the following proof we restrict our attention only to the rows and

columns of Re . First note that a fraction of at least c/2d of the rows contain at

a fraction of at least c/2d zero entries (otherwise the fraction of zero entries in

Re is less than c/2d · 1 + (1 ’ c/2d) · c/2d < c/d). Thus, the number of rows with

at least c|V |/(2w2 d) zero entries is at least c|U |/(8d). We will show that these

rows contain many distinct rows, which will imply that Re has rank ©(n0.5 ).

Fix any row u0 of Re with at least c|V |/(2w2 d) zero entries. We show that

the row u0 can only appear in Re a small number of times (labeled by di¬erent

u™s ). Let M be the set of columns in which this row has zero entries; the size of

M is at least c|V |/(4d). Let e = (x, y), where x belongs to layer Lj for some j

and y ∈ Lj+1 .

We ¬rst prove that M contains a subset M of paths of size · w for some

su¬ciently small constant (to be ¬xed later) such that every two paths in M

6

This is the number of entries if x ∈ L1 , otherwise this number is |U |/4 · |V |/w2 .

180 A. Beimel and A. Paskin

have no nodes in common except for x, y, s, t. Similarly to the proof of Lemma 2,

we construct this set iteratively. In the ¬rst iteration, we add to M some arbi-

trary path in M . We continue adding paths until there are w paths. In iteration

i + 1, we have added i paths to M . We prove that another path can be added

so that all the paths in M satisfy the invariant of being disjoint up to including

s, x, y, t. Any path using one of the w ’ i unused nodes in every layer Lk , where

k = j, j + 1, can be used here. The number of all columns of Re with this prop-

erty is at least (w ’ i)d’2 ≥ (w(1 ’ ))d’2 , thus the number of columns in Re

violating this property is at most

wd’2 ’(w(1’ ))d’2 = wd’2 (1’(1’ )d’2 ) ≈ wd’2 (d’2) = |V | (d’2) < |V | d.

(for a su¬ciently small constant ). Taking ¤ c/(4d2 ), there are at least

c|V |/(4d) ’ |V | d > 1 paths in M satisfying this property.

Having proved M = v1 , . . . , v |M| as above exists, we consider the set of

rows

B = {u : e ∈ u and |S(u, v)| > 1 for every v ∈ M }.

/

Notice that for every u ∈ B , where e ∈ u, there exists a v ∈ M such that

/ /

|S(u, v)| = 1, thus, by Obseration 1, Re (u, v) = 1, however, Re (u0 , v) = 0

since v ∈ M (where M is the set of columns with zero entries in the row u0 ).

Thus, B is the set of rows in Re that can be equal to the row u0 . Recall that

e = (x, y) ∈ S(u, v) for every row u of Re and every column v of Re (by the

de¬nition of Re ). Thus, S(u, v) > 1 if the cut u does not contain at least one

edge on the path v in addition to the edge (x, y).

We next show that B is of negligible size. We do this by calculating the prob-

ability that a cut chosen with uniform distribution is B . We choose a random

cut u = (S, T ) by ¬rst choosing for each node in v1 if its in S or in T , then the

nodes corresponding to v2 , and so on, where the inclusion in S or T is selected

at random according to the proportion of the remaining colors for that layer

(conditioned on the choices for the previous vi ™s). The cut u forms a singleton

with a given vi , selected in iterations i, if the node in vi from Lk for j ¤ j are in

S, and the rest of the nodes in vi are in T . This happens with probability at least

def

(1/2 ’ )d’2 = 1 ’ f . Thus, with probability at most f the cut u does not form

a singleton with a given vi . Note f is some constant. Therefore, |S(u, v)| > 1 for

every v ∈ M with probability at most

f |M | = f = 2’θ(w) .

w

This implies that the size of B is at most 2’θ(w) |U |/2.

Since there are at least c|U |/(4d) rows with a fraction of at least c/(2d) zeros,

and each such row can appear at most 2’θ(w)|U |/2 in Re , the number of distinct

rows in Re is at least

c|U |/(4d)

= 2θ(w).

’θ(w) |U |/2

2

This implies that rankGF(2) (Fe ) = rankGF(2) (Re ) = log(2θ(w)) = θ(w) = θ(n0.5 ).

On Linear Secret Sharing for Connectivity in Directed Graphs 181

By Lemma 2 and Lemma 3, there are ©(n) matrices Fe such that

rankGF(2) (Fe ) = θ(n0.5 ).

Thus, by Theorem 3, every monotone span program computing st-con has size

©(n1.5 ).