Paper 2009/059

On the impossibility of graph secret sharing

Laszlo Csirmaz


A {\it 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) {\it 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
secret sharinginformation theory
Contact author(s)
csirmaz @ degas ceu hu
2009-02-06: received
Short URL
Creative Commons Attribution


      author = {Laszlo Csirmaz},
      title = {On the impossibility of graph secret sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2009/059},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.