One of the main open problems in secret sharing is the characterization of the ideal access structures. This problem has been studied for several families of access structures with similar results. Namely, in all these families, the ideal access structures coincide with the vector space ones and, besides, the optimal information rate of a non-ideal access structure is at most 2/3. An access structure is said to be r-homogeneous if there are exactly r participants in every minimal qualified subset. A first approach to the characterization of the ideal 3-homogeneous access structures is made in this paper. We show that the results in the previously studied families can not be directly generalized to this one. Nevertheless, we prove that the equivalences above apply to the family of the sparse 3-homogeneous access structures, that is, those in which any subset of four participants contains at most two minimal qualified subsets. Besides, we give a complete description of the ideal sparse 3-homogeneous access structures.
The characterization of ideal access structures and the search for bounds on the optimal information rate are two important problems in secret sharing. These problems are studied in this paper for access structures with intersection number equal to one, that is, access structures such that there is at most one participant in the intersection of any two different minimal qualified subsets. The main result in this work is the complete characterization of the ideal access structures with intersection number equal to one. Besides, bounds on the optimal information rate are provided for the non-ideal case.
Starting from a new relation between graphs and secret sharing schemes introduced by Xiao, Liu and Zhang, we show a method to construct more general ideal homogeneous access structures. The method has some advantages: it efficiently gives an ideal homogeneous access structure for the desired rank, and some conditions can be imposed (such as forbidden or necessary subsets of players), even if the exact composition of the resulting access structure cannot be fully controlled. The number of homogeneous access structures that can be constructed in this way is quite limited; for example, we show that (t, )-threshold access structures can be constructed from a graph only when t = 1, t = − 1 or t = .
A perfect secret-sharing scheme is a method to distribute a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of participants in any unqualified subset is statistically independent of the secret. The collection of all qualified subsets is called the access structure of the perfect secret-sharing scheme. In a graph-based access structure, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme realizing the access structure based on G is defined as AR = (Pv2V (G) H(v))/(|V (G)|H(s)), where s is the secret and v is the share of v, both are random variables from and H is the Shannon entropy. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing a given access structure is called the optimal average information ratio of that access structure. Most known results about the optimal average information ratio give upper bounds or lower bounds on it. In this present structures based on bipartite graphs and determine the exact values of the optimal average information ratio of some infinite classes of them.
In a perfect secret-sharing scheme, a dealer distributes a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of the participants in any unqualified subset is statistically independent of the secret. The access structure of the scheme refers to the collection of all qualified subsets. In a graph-based access structures, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme realizing a given access structure is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal average information ratio of that access structure. We study the optimal average information ratio of the access structures based on bipartite graphs. Based on some previous results, we give a bound on the optimal average information ratio for all bipartite graphs of girth at least six. This bound is the best possible for some classes of bipartite graphs using our approach.
A secret-sharing scheme realizes the forbidden graph access structure determined by a graph
G=(V,E)if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in
E(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with
nvertices and at most
n1+βedges (resp. at least
(2n)−n1+βedges), for some
0≤β<1, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size
O~(n1+β/2). Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is
O~(n1/4+β/4). We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size
Ω(n3/2); this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every
0≤β<1there exist a graph with at most
n1+βedges and a graph with at least
(2n)−n1+βedges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is
Ω(n1+β/2). Finally, we show that for every
0≤β<1there exist a graph with at most
n1+βedges and a graph with at least
(2n)−n1+βedges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is
Ω(n1/4+β/4). This shows that our constructions are optimal (up to poly-logarithmic factors).