###
L. Csirmaz:

##
On the impossibility of graph secret sharing

A *perfect secret sharing scheme* based on a graph *G* is a randomized
distribution of a secret among the vertices of the graph so that the secret
can be recovered from the information assigned to vertices at the endpoints
of any edge, while the total information assigned to an independent set of
vertices is independent (in statistical sense) of the secret itself.

The efficiency of a scheme is measured by the amount of information the
most heavily loaded vertex receives divided by the amount of information
in the secret
itself. The (worst case) *information ratio* of *G* is the infimum of
this number. We calculate the best lower bound on the information ratio
for an infinite family of graphs the celebrated entropy method can give.

We argue that all existing constructions for secret sharing schemes are
special cases of the generalized vector space construction. We give
direct constructions of this type for the first two members of the family,
and show that for the other members no construction exists
which would match the bound yielded by the entropy method.

Full paper(PDF, 180k)