[Resource Topic] 2005/059: Secret sharing schemes on graphs

Welcome to the resource topic for 2005/059

Secret sharing schemes on graphs

Authors: Laszlo Csirmaz


Given a graph G, a perfect secret sharing scheme based on G is a method to distribute a secret data among the vertices of G, the participants, so that a subset of participants can recover the secret if they contain an edge of G, otherwise they can obtain no information regarding the secret. The average information rate is the ratio of the size of the secret and the average size of the share a participant must remember. The information rate of G is the supremum of the information rates realizable by perfect secret sharing schemes.

We construct a graph on n vertices with average information rate below 4/\log n. We obtain this result by determining, up to a constant factor, the average information rate of the d/dimensional cube.

ePrint: https://eprint.iacr.org/2005/059

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .