Ideal secret sharing schemes on graph-based 3 -homogeneous access structures

The characterization of the ideal access structures is one of the main open problems in secret sharing and is important from both practical and theoretical points of views. A graph-based 3−homogeneous access structure is an access structure in which the participants are the vertices of a connected graph and every subset of the vertices is a minimal qualified subset if it has three vertices and induces a connected graph. In this paper, we introduce the graph-based 3−homogeneous access structures and characterize the ideal graph-based 3-homogeneous access structures. We prove that for every non-ideal graph-based 3-homogeneous access structure over the graph G with the maximum degree d there exists a secret sharing scheme with an information rate 1d+1. Furthermore, we mention three forbidden configurations that are useful in characterizing other families of ideal access structures.