Optimal assignment schemes for general access structures based on linear programming

The paper proposes a type of secret sharing schemes called ramp assignment schemes (RAS’s) to realize general access structures (AS’s). In such a scheme, each participant is assigned a subset of primitive shares of an optimal (k,L,m)-ramp scheme in such a way that the number of primitive shares assigned to each qualified subset is not less than k whereas the one corresponding to any forbidden subset is not greater than k-L. RAS’s can be viewed as a generalization of multiple assignment schemes (MAS’s). For a same AS, the minimum information rate achieved by MAS’s can not be less than that achieved by RAS’s. With our method, one can find efficient suitable decompositions for general AS’s. And it provides a possibility to refine an existing (λ,ω)-decomposition. We show that a RAS with minimal worst or/and average information rate can be obtained by linear programming (LP), which is in the complexity class P and much easier than the NP-hard integer programming (IP) applied to constructing optimal MAS’s. Several well-designed algorithms are further presented to cut down the size of the LP/IP problems for optimal RAS’s/MAS’s. Other contributions of the paper include: (1) the current best upper bounds of information rates of two graph AS’s on six participants are improved; (2) some specific AS’s are recognized so that one can obtain the corresponding optimal RAS’s directly, i.e., even without the need of solving LP problems; and (3) we characterize the AS’s of ideal RAS’s and of ideal MAS’s.