Paper 2009/071

Secret sharing on trees: problem solved

Laszlo Csirmaz and Gabor Tardos

Abstract

We determine the worst case information rate for all secret sharing schemes based on trees. It is the inverse of 21/c, where c is the size of the maximal core in the tree. A {\it 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 is also the {\it 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 algorithm which finds an optimal cover on any tree, and thus a perfect secret sharing scheme with optimal rate.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Secret sharing schemeinformation rategraph
Contact author(s)
csirmaz @ degas ceu hu
History
2009-02-16: received
Short URL
https://ia.cr/2009/071
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/071,
      author = {Laszlo Csirmaz and Gabor Tardos},
      title = {Secret sharing on trees: problem solved},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/071},
      year = {2009},
      url = {https://eprint.iacr.org/2009/071}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.