The Average Information Ratio of Secret-Sharing Schemes for Access Structures Based on Coalescence of Graphs

摘要

A perfect secret-sharing scheme is a method of distributing a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the participants in any unqualified subset cannot obtain any information about the secret. The collection of all qualified subsets is called the access structure of the scheme. In a graph-based access structure, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme realizing a given access structure is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal average information ratio of that access structure. In this paper, we study the optimal average information ratio of access structures based on coalescence graphs. We investigate how the optimal average information ratio changes under graph coalescence.