Abstract
A perfect secret sharing scheme for a prohibited structure is a method of sharing a master key among a finite set of participants in such a way that only certain pre-specified subsets of participants cannot recover the master key. A secret sharing scheme is called perfect if any subset of participants who cannot recover the master key obtains no information regarding the master key. In this paper, we propose a new construction for perfect secret sharing schemes with graph-based prohibited structures. Given a prohibited graph G, the information rate of the constructed perfect secret sharing scheme is at least max{2/(deg(Ḡ)+3), 2/n}, where deg(Ḡ) is the maximum degree of the complement of G and n is the number of vertices of G. Compared with the previous construction, our construction has an improvement on the information rate.