In a secret sharing scheme a piece of information – the secret –is distributed among a finite set of participants, such that only some predefinedcoalitions can recover it. This set of subsets is supposed to be monotone, hence thesystem can be characterized by its minimal elements. From this point of view, asecret sharing scheme can be described with a hypergraph where the hyperedgesare these minimal elements. The efficiency of the scheme is measured by theamount of information the most heavily loaded participant must remember. Thisamount is called complexity and one of the most interesting problem of this topicis the characterization of systems of complexity 1, or ideal structures.We outline some results about 2-uniform hypergraphs (i.e. graph-based systems)and discuss the generalizations of the respective known results for 3-uniformhypergraphs, where every hyperedge contains exactly 3 participants. We presentseveral families of ideal systems, disprove an older characterization of ideal hyperstarsand demonstrate the strength of the so-called forbidden minor characterizationmethod by describing the forbidden 3-uniform sub-hypergraphs of idealhypergraphs.
@article{198,
title = {On secret sharing and 3-uniform hypergraphs},
journal = {Tatra Mountains Mathematical Publications},
volume = {51},
year = {2012},
doi = {10.2478/tatra.v53i0.198},
language = {EN},
url = {http://dml.mathdoc.fr/item/198}
}
Ligeti, Péter. On secret sharing and 3-uniform hypergraphs. Tatra Mountains Mathematical Publications, Tome 51 (2012) . doi : 10.2478/tatra.v53i0.198. http://gdmltest.u-ga.fr/item/198/