AN EFFICIENT CONSTRUCTION OF PERFECT SECRET SHARING SCHEMES FOR GRAPH-BASED STRUCTURES

In this paper, we propose an efficient construction of perfect secret sharing schemes for graph-based access structures where a vertex denot es a participant and an edge does a qualified pair of participants. Th e secret sharing scheme is based on the assumptions that the pairs of participants corresponding to edges in the graph can compute the maste r key but the pairs of participants corresponding to nonedges in the g raph cannot. The information rate of our scheme is 1/(n-1), where n is the number of participants. We also present an application of our sch eme to the reduction of storage and computation loads on the communica tion granting server in a secure network.