### 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.

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.

DOI: https://doi.org/10.2478/tatra.v53i0.198