Secret sharing schemes on graphs
Secret sharing schemes on graphs
L. Csirmaz:
Secret sharing schemes on graphs
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 key. 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.
Based on the entropy-theoretical arguments due to Capocelli et al, and
extending the results of M. van Dijk, 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.