Paper 2012/245 Original: eprint.iacr.org/2012/245 ↗

On the Equivalence between the Set Covering Problem and the Problem of Finding Optimal Cumulative Assignment Schemes

Abstract

A cumulative assignment scheme (CAS for short) is a special type of secret sharing schemes. For any given access structure (AS), a CAS which minimizes the cardinality of the primitive share set (the average information rate, or the worst information rate) is called an optimal CAS and can be constructed via solving some binary integer programming (BIP). The problem of finding optimal CAS's for complete AS's is solved. We consider in this paper the problem of finding optimal CAS's for incomplete AS's. The paper introduces some notions including the connected-super-forbidden-family and the lower-forbidden-family for AS's. We show that an optimal CAS can be derived from some smaller sized BIP whose variables (constraints, resp.) are based on the connected-super-forbidden-family (lower-forbidden-family, resp.) of the given AS. The paper further builds the close relationship between the problem of finding optimal CAS's and the set covering problem (SCP). We prove that the problem of finding a CAS with minimum cardinality of the primitive share set (or minimum average information rate) is equivalent to the SCP, and thus is NP-hard. Other contributions of the paper include: 1) two types of AS's are recognized so that we can construct the corresponding optimal CAS's directly; and 2) a greedy algorithm is proposed to find CAS's with smaller worst information rate.