Nanyang Technological University
Optimizing the ratio between the maximum length of the shares and the length of the secret value in secret sharing schemes for general access structures is an extremely difficult and long-standing open problem. In this paper, the authors study it for bipartite access structures, in which the set of participants is divided in two parts, and all participants in each part play an equivalent role. They focus on the search of lower bounds by using a special class of polymatroids that is introduced here, the tripartite ones. They present a method based on linear programming to compute, for every given bipartite access structure, the best lower bound that can be obtained by this combinatorial method.