We determine the worst case information rate for all secret sharing schemes based on trees. It is the inverse of 2-1/c, where c is the size of the maximal core in the tree. A core is a connected subset of the vertices so that every vertex in the core has a neighbor outside the core. The upper bound comes from an application of the entropy method, while the lower bound is achieved by a construction using Stinson's decomposition theorem.
It is shown that 2-1/c is also the fractional cover number of the tree where the edges of the tree are covered by stars, and the vertex cover should be minimized. We also give an O(n2) algorithm which finds an optimal cover on any tree, and thus a perfect secret sharing scheme with optimal rate.
Keywords. Secret sharing scheme; information rate; graph; fractional packing and cover; entropy method.
Full paper(PDF, 150k)