𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Combinatorial lower bounds for secret sharing schemes

✍ Scribed by Kaoru Kurosawa; Koji Okada

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
286 KB
Volume
60
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

In a perfect secret sharing scheme, it holds that log, I%[ > H(S), where S denotes the secret and G denotes the set of the share of user i. On the other hand, it is well known that log213 > H(S) if S is not uniformly distributed, where ? denotes the set of secrets. In this case, log, @I > H(S) < log, ISI. Then, which is bigger, @I or lq? We first prove that I%( 2 ISI for any distribution on S by using a combinatorial argument. This is a more sharp lower bound on $1 for not uniformly distributed S. Our proof makes it intuitively clear why [VI must be so large. Next, we extend our technique to show that maxi log, [cl > 1.5 log, ISI for some access structure.

πŸ“œ SIMILAR VOLUMES

Lower bounds on the information rate of
Lower bounds on the information rate of secret sharing schemes with homogeneous access structure
✍ Carles PadrΓ³; GermΓ‘n SΓ‘ez πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 81 KB

We present some new lower bounds on the optimal information rate and on the optimal average information rate of secret sharing schemes with homogeneous access structure. These bounds are found by using some covering constructions and a new parameter, the k-degree of a participant, that is introduced

Recursive constructions for perfect secr
Recursive constructions for perfect secret sharing schemes
✍ Hung-Min Sun; Shiuh-Pyng Shieh πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 595 KB

A secret sharing scheme is a method which allows a secret to be shared among a set of participants in such a way that only qualified subsets of participants can recover the secret. A secret sharing scheme is called perfect if unqualified subsets of participants obtain no information regarding the se

New combinatorial designs and their appl
New combinatorial designs and their applications to authentication codes and secret sharing schemes
✍ Wakaha Ogata; Kaoru Kurosawa; Douglas R. Stinson; Hajime Saido πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 306 KB

This paper introduces three new types of combinatorial designs, which we call external difference families (EDF), external BIBDs (EBIBD) and splitting BIBDs. An EDF is a special type of EBIBD, so existence of an EDF implies existence of an EBIBD. We construct optimal splitting A-codes by using EDF.