Paper 2012/245

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

Qiang Li, Xiangxue Li, Dong Zheng, Zheng Huang, and 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Cumulative assignment schemeIncomplete access structureSet covering problemNP-Hard
Contact author(s)
qiangl @ sjtu edu cn
History
2012-05-03: received
Short URL
https://ia.cr/2012/245
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/245,
      author = {Qiang Li and Xiangxue Li and Dong Zheng and Zheng Huang and Kefei Chen},
      title = {On the Equivalence between the Set Covering Problem and the Problem of Finding Optimal Cumulative Assignment Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/245},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/245}},
      url = {https://eprint.iacr.org/2012/245}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.