Smallest graphs achieving the Stinson bound
This work addresses the efficiency of secret sharing schemes in cryptography by providing more compact graph constructions, representing an incremental improvement over prior results.
The paper tackles the problem of constructing graphs for perfect secret sharing schemes that achieve the Stinson bound on information ratio, and it results in a new family of graphs with significantly fewer vertices, specifically reducing from at least c·6^δ to c·2^δ vertices while maintaining the same bound.
Perfect secret sharing scheme is a method of distribute a secret information $s$ among participants such that only predefined coalitions, called qualified subsets of the participants can recover the secret, whereas any other coalitions, the unqualified subsets cannot determine anything about the secret. The most important property is the efficiency of the system, which is measured by the information ratio. It can be shown that for graphs the information ratio is at most $(δ+1)/2$ where $δ$ is the maximal degree of the graph. Blundo et al. constructed a family of $δ$-regular graphs with information ratio $(δ+1)/2$ on at least $c\cdot 6^δ$ vertices. We improve this result by constructing a significantly smaller graph family on $c\cdot 2^δ$ vertices achieving the same upper bound both in the worst and the average case.