Abstract
A secret sharing scheme is a method which allows a secret to be shared among a finite set of participants in such a way that only qualified subsets of participants can recover it. A secret sharing scheme is called perfect if unqualified subsets of participants obtain no information about the secret. The authors propose an efficient construction of perfect secret sharing schemes for the access structures consisting of the closure of a graph where a vertex denotes a participant and an edge denotes a minimal qualified pairs of participants. The information rate of the scheme is at least 1/(2|P|), where P denotes the set of the participants, which is better than O(1/|P|/sup 2/) of existing schemes used for graph-based access structures. The authors also present an application of the scheme to the reduction of storage and computation loads on the key distribution server in a secure network.