Abstract: In a perfect secret-sharing scheme, a dealer distributes
a secret among a set of participants in such a way that only qualified
subsets of participants can recover the secret and the joint share of the
participants in any unqualified subset is statistically independent of
the secret. The access structure of the scheme refers to the collection
of all qualified subsets. In a graph-based access structures, 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. We study the optimal average information ratio of the
access structures based on bipartite graphs. Based on some previous
results, we give a bound on the optimal average information ratio
for all bipartite graphs of girth at least six. This bound is the best
possible for some classes of bipartite graphs using our approach.
Abstract: A perfect secret-sharing scheme is a method to distribute a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of participants in any unqualified subset is statistically independent of the secret. The collection of all qualified subsets is called the access structure of the perfect secret-sharing 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 the access structure based on G is defined as AR = (Pv2V (G) H(v))/(|V (G)|H(s)), where s is the secret and v is the share of v, both are random variables from and H is the Shannon entropy. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing a given access structure is called the optimal average information ratio of that access structure. Most known results about the optimal average information ratio give upper bounds or lower bounds on it. In this present structures based on bipartite graphs and determine the exact values of the optimal average information ratio of some infinite classes of them.