TY - JOUR

T1 - New bounds on the average information rate of secret-sharing schemes for graph-based weighted threshold access structures

AU - Lu, Hui Chuan

AU - Fu, Hung-Lin

PY - 2013/8/10

Y1 - 2013/8/10

N2 - A secret-sharing scheme is a protocol by which a dealer distributes shares of a secret key among a set of n participants in such a way that only qualified subsets of participants can reconstruct the secret key from the shares they received, while unqualified subsets have no information about the secret key. The collection of all qualified subsets is called the access structure of this scheme. The information rate (resp. average information rate) of a secret-sharing scheme is the ratio between the size of the secret key and the maximum size (resp. average size) of the shares. In a weighted threshold scheme, each participant has his or her own weight. A subset is qualified if and only if the sum of the weights of participants in the subset is not less than the given threshold. Morillo et al. [19] considered the schemes for weighted threshold access structure that can be represented by graphs called k-weighted graphs. They characterized this kind of access structures and derived a result on the information rate. In this paper, we deal with the average information rate of the secret-sharing schemes for these structures. Two sophisticated constructions are presented, each of which has its own advantages and both of them perform very well when n/k is large.

AB - A secret-sharing scheme is a protocol by which a dealer distributes shares of a secret key among a set of n participants in such a way that only qualified subsets of participants can reconstruct the secret key from the shares they received, while unqualified subsets have no information about the secret key. The collection of all qualified subsets is called the access structure of this scheme. The information rate (resp. average information rate) of a secret-sharing scheme is the ratio between the size of the secret key and the maximum size (resp. average size) of the shares. In a weighted threshold scheme, each participant has his or her own weight. A subset is qualified if and only if the sum of the weights of participants in the subset is not less than the given threshold. Morillo et al. [19] considered the schemes for weighted threshold access structure that can be represented by graphs called k-weighted graphs. They characterized this kind of access structures and derived a result on the information rate. In this paper, we deal with the average information rate of the secret-sharing schemes for these structures. Two sophisticated constructions are presented, each of which has its own advantages and both of them perform very well when n/k is large.

KW - Access structure Optimal information rate

KW - Complete multipartite covering

KW - Optimal average information rate

KW - Secret-sharing scheme

KW - Weighted threshold access structure

UR - http://www.scopus.com/inward/record.url?scp=84877716250&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2013.03.047

DO - 10.1016/j.ins.2013.03.047

M3 - Article

AN - SCOPUS:84877716250

VL - 240

SP - 83

EP - 94

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

ER -