Optimal assignment schemes for general access structures based on linear programming
The paper proposes a type of secret sharing schemes called ramp assignment schemes (RASs) to realize general access structures (ASs). 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\). RASs can be viewed as a generalization of multiple assignment schemes (MASs). For a same AS, the minimum information rate achieved by MASs can not be less than that achieved by RASs. With our method, one can find efficient suitable decompositions for general ASs. And it provides a possibility to refine an existing \((\lambda ,\omega )\)-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 MASs. Several well-designed algorithms are further presented to cut down the size of the LP/IP problems for optimal RASs/MASs. Other contributions of the paper include: (1) the current best upper bounds of information rates of two graph ASs on six participants are improved; (2) some specific ASs are recognized so that one can obtain the corresponding optimal RASs directly, i.e., even without the need of solving LP problems; and (3) we characterize the ASs of ideal RASs and of ideal MASs.
ramp assignment scheme multiple assignment scheme information rate secret sharing (94a62) linear/integer programming 94a62 94a60