On secret sharing and 3-uniform hypergraphs

Abstract

In a secret sharing scheme a piece of information – the secret –
is distributed among a finite set of participants, such that only some predefined
coalitions can recover it. This set of subsets is supposed to be monotone, hence the
system can be characterized by its minimal elements. From this point of view, a
secret sharing scheme can be described with a hypergraph where the hyperedges
are these minimal elements. The efficiency of the scheme is measured by the
amount of information the most heavily loaded participant must remember. This
amount is called complexity and one of the most interesting problem of this topic
is 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-uniform
hypergraphs, where every hyperedge contains exactly 3 participants. We present
several families of ideal systems, disprove an older characterization of ideal hyperstars
and demonstrate the strength of the so-called forbidden minor characterization
method by describing the forbidden 3-uniform sub-hypergraphs of ideal
hypergraphs.