Abstract
Secret sharing schemes are methods for distributing a secret among qualified subsets of participants without revealing any information about the secret to unqualified participants. In 1994, Stinson proposed the decomposition constructions for secret sharing schemes, in which coefficients of the secret sharing schemes are determined by solving a suitable linear programming problem. However, listing the linear programming problem is a complex and inefficient task when the number of participants is large. To account for this defect, this thesis presents a novel decomposition approach for perfect secret sharing schemes with general access structures. This method exploits a different approach for avoiding the predicament in the listing of the feasible star-based scheme of the linear programming problem in Stinson’s method. In our approach, all edges in the access structure are modified as vectors instead of multipartite subgraphs as in Stinson’s subjects of linear programming problem. After determining the coefficients in our linear programming problem, a hierarchical decomposition can be constructed in relation to the result of the coefficients of these vectors. The proposed method can determine optimal decompositions with the same information rate as Stinson’s method with K1,n. With the new decomposition constructions, we improve the running time for the decomposition of the access structure with K1,n in Stinson’s method from exponential-time complexity (O(L(2|E||V|+22|E|)(2|E|+(|V|+2|E|)0.5))) to polynomial-time complexity (O (L|E|3+ |V|2log|V| )), where |E| and |V| are the numbers of edges and vertices in the graph that represents the access structure, and L is the number of bits needed to represent all the coefficients.