We derive new limitations on the information rate and the average information rate of secret sharing schemes for access structure represented by graphs. We give the first proof of the existence of access structures with optimal information rate and optimal average information rate less that 1=2 + ffl, where ffl is an arbitrary positive constant. We also consider the problem of testing if one of these access structures is a sub-structure of an arbitrary access structure and we show that this problem is NP-complete. We provide several general lower bounds on information rate and average information rate of graphs. In particular, we show that any graph with n vertices admits a secret sharing scheme with information rate\Omega\Gammate/3 n)=n). 1 Introduction A secret sharing scheme is a method to distribute a secret s among a set of participants P in such a way that only qualified subsets of P can reconstruct the value of s

On the Information Rate of Secret Sharing Schemes

BLUNDO, Carlo;DE SANTIS, Alfredo;GARGANO, Luisa;VACCARO, Ugo
1996

Abstract

We derive new limitations on the information rate and the average information rate of secret sharing schemes for access structure represented by graphs. We give the first proof of the existence of access structures with optimal information rate and optimal average information rate less that 1=2 + ffl, where ffl is an arbitrary positive constant. We also consider the problem of testing if one of these access structures is a sub-structure of an arbitrary access structure and we show that this problem is NP-complete. We provide several general lower bounds on information rate and average information rate of graphs. In particular, we show that any graph with n vertices admits a secret sharing scheme with information rate\Omega\Gammate/3 n)=n). 1 Introduction A secret sharing scheme is a method to distribute a secret s among a set of participants P in such a way that only qualified subsets of P can reconstruct the value of s
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/3136579
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 40
  • ???jsp.display-item.citation.isi??? 33
social impact