New construction of perfect secret sharing schemes for graph-based prohibited structures

A perfect secret sharing scheme for a prohibited structure is a method of s haring a master key among a finite set of participants in such a way that o nly certain pre-specified subsets of participants cannot recover the master key. A secret sharing scheme is called perfect if any subset of participan ts who cannot recover the master key obtains no information regarding the m aster key. In this paper, we propose a new construction for perfect secret sharing schemes with graph-based prohibited structures. Git en a prohibited graph G, the information rate of the constructed perfect secret sharing sc heme is at least max{2/(deg((G) over bar) + 3), 2/n}, where deg((G) over ba r) is the maximum degree of the complement of G and n is the number of vert ices of G. Compared with the previous construction, our construction has an improvement on the information rate. (C) 1999 Elsevier Science Ltd. All ri ghts reserved.