We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participantmustrememberforeachbitinthesecret -- justtheinverseoftheinformationrate. Wedeterminethisvalueforseveralin honeycomb lattices; and give upper and finite graphs: lower bounds in on finite path, two-dimensional square and It is also shown that the information ratio is not necessarily the ratio local, for the i.e. triangular all nite spanned lattice. subgraphs have strictly smaller ratio than the whole graph. several open problems.
We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participantmustrememberforeachbitinthesecret -- justtheinverseoftheinformationrate. Wedeterminethisvalueforseveralin honeycomb lattices; and give upper and finite graphs: lower bounds in on finite path, two-dimensional square and It is also shown that the information ratio is not necessarily the ratio local, for the i.e. triangular all nite spanned lattice. subgraphs have strictly smaller ratio than the whole graph. several open problems.
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.
Secret sharing is a method to distribute a secret amongst participants, such that only some predefined coalitions, called qualified sets can recover the secret. The set of the qualified subsets is called the access structure, and if all minimally qualified sets have two elements then the access structure is representable by a graph. The information ratio of an access structure is the amount of information the most overloaded participant must remember per secret bit. In this paper, we compute the information ratio of the unicyclic graph, i.e., connected graphs that are arising from a tree by adding an edge between two non-connected vertices.
In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by k2k−1⋅H(s), where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a L1 fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of kL2k−1⋅H(s), under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely k2k−2+1/L⋅H(s), which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.
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 d+11. Furthermore, we mention three forbidden configurations that are useful in characterizing other families of ideal access structures.
Abstract The efficiency of a secret sharing scheme is measured via its information ratio. The optimal information ratio (OIR) of an access structure is the infimum of the information ratios of all secret sharing schemes realizing it. When the infimum is taken over all linear secret sharing schemes, it is called the optimal linear information ratio (OLIR). We review the problem of finding the OIRs and OLIRs of graph access structures on six participants. Study of such access structures was initiated by van Dijk et al. (1998) [43] . In a sequence of works, the OIRs of nine access structures, out of the 18 initially unsolved non-isomorphic ones, were determined. Very recently, the known lower bounds on the OLIRs of the other nine cases have been improved (Farras et al., 2018 [20] ), determining the OLIRs for another two cases. In this paper, for each of the remaining seven cases, we provide a new upper bound on the OIR which matches that of the recently found lower bound on the OLIR. Improved upper bounds are achieved by constructing a linear secret sharing scheme, using a suitable decomposition technique for each access structure. A new decomposition technique, called ( λ , ω ) -weighted decomposition, is also introduced which is a generalization of all known decomposition methods.