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.
Category / Keywords: foundations / secret sharing, information theory Date: received 5 Feb 2009 Contact author: csirmaz at degas ceu hu Available formats: PDF | BibTeX Citation Version: 20090206:143919 (All versions of this report) Discussion forum: Show discussion | Start new discussion