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

Abstract

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. (C) 2013 Elsevier Inc. All rights reserved.