ON THE INFORMATION RATE OF SECRET SHARING SCHEMES

We derive new limitations on the information rate and the average info rmation rate of secret sharing schemes for access structure represente d by graphs. We give the first proof of the existence of access struct ures with optimal information rate and optimal average information rat e less than 1/2+epsilon, where epsilon is an arbitrary positive consta nt. We also consider the problem of testing if one of these access str uctures is a substructure of an arbitrary access structure and we show that this problem is NP-complete. We provide several general lower bo unds on information rate and average information rate of graphs. In pa rticular, we show that any graph with n vertices admits a secret shari ng scheme with information rate Omega((log n)/n).