International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 03 May 2012

Qiang Li, Xiangxue Li, Dong Zheng, Zheng Huang, Kefei Chen
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.