Ideal secret sharing schemes on graph-based $3$-homogeneous access structures
نویسندگان
1 Department of Mathematics and Cryptography, Malek Ashtar University of Technology, Isfahan, Iran
2 Electrical and computer faculty, Malek Ashtar University of Technology, Tehran, Iran
3 Department of Mathematics and Cryptography, Malek Ashtar University of Technology, Isfahan, Iran
doi
10.22108/toc.2021.123661.1739چکیده
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 $\frac{1}{d+1}$. Furthermore, we mention three forbidden configurations that are useful in characterizing other families of ideal access structures.
