Title: Some improved bounds on the information rate of perfect secret sharing schemes
Abstract: In this paper we study secret sharing schemes for access structures based on graphs. A secret sharing scheme enables a secret key to be shared among a set of participants by distributing partial information called shares. Suppose we desire that some specified pairs of participants be able to compute the key. This gives rise in a natural way to a graphG which contains these specified pairs as its edges. The secret sharing scheme is calledperfect if a pair of participants corresponding to a nonedge ofG can obtain no information regarding the key. Such a perfect secret sharing scheme can be constructed for any graph. In this paper we study the information rate of these schemes, which measures how much information is being distributed as shares compared with the size of the secret key. We give several constructions for secret sharing schemes that have a higher information rate than previously known schemes. We prove the general result that, for any graphG having maximum degreed, there is a perfect secret sharing scheme realizingG in which the information rate is at least 2/(d+3). This improves the best previous general bound by a factor of almost two.