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

Hui Chuan Lu*, Hung-Lin Fu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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.

Original languageEnglish
Pages (from-to)83-94
Number of pages12
JournalInformation sciences
Volume240
DOIs
StatePublished - 10 Aug 2013

Keywords

  • Access structure Optimal information rate
  • Complete multipartite covering
  • Optimal average information rate
  • Secret-sharing scheme
  • Weighted threshold access structure

Fingerprint Dive into the research topics of 'New bounds on the average information rate of secret-sharing schemes for graph-based weighted threshold access structures'. Together they form a unique fingerprint.

Cite this