Welcome to the resource topic for 2012/245
Title:
On the Equivalence between the Set Covering Problem and the Problem of Finding Optimal Cumulative Assignment Schemes
Authors: Qiang Li, Xiangxue Li, Dong Zheng, Zheng Huang, Kefei Chen
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.
ePrint: https://eprint.iacr.org/2012/245
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .