Tight bounds on the information rate of secret sharing schemes (Q1358672)

Secret sharing schemes represent a useful tool to ensure that some secret value is available only as a result of collaborative effort of some qualified set of participants, while preventing other sets of participants to determine anything about the secret value. A secret sharing scheme requires that some shares are distributed among the set of participants in an appropriate way. In practice the information rate of the scheme, i.e. the ratio between the size of the secret and that of the largest share given to any participant, form an important parameter of the scheme. Previous results on upper bounds on the information rate have used rather ad hoc proof techniques. In the paper a general technique to derive upper bounds on the information rate of secret sharing schemes is given. It is also noted that the method cannot provide an upper bound better than \(({\log n}) / n\). Finally, a tight upper bound on the information rate for an infinite class of graph-based access structures is proved.