SECRET SHARING SCHEMES FOR GRAPH-BASED PROHIBITED STRUCTURES

A secret sharing scheme for the prohibited structure is a method of sh aring a master key among a finite set of participants in such a way th at only certain prespecified subsets of participants cannot recover th e master key. A secret sharing scheme is called perfect, if any subset of participants who cannot recover the master key obtains no informat ion regarding the master key. In this paper, we propose an efficient c onstruction of perfect secret sharing schemes for graph-based prohibit ed structures where a vertex denotes a participant and an edge does a pair of participants who cannot recover the master key. The informatio n rate of our scheme is 2/n, where n is the number of participants. (C ) 1998 Elsevier Science Ltd. All rights reserved.