Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Advanced materials research

The Optimal Information Rates of the Graph Access Structures on Seven Participants

Zhi Hui Li, Yun S. Song, Yong Li

Published Dec 1, 2013• 1 citation
Publisher

Abstract

The information rate is an important metric of the performance of a secret-sharing scheme. In this paper, we deal with determining the exact values for the optimal information rates of the six graph access structures and improving the information rate of a graph access structure on seven participants, which remained as open problems in Song's and Wang's paper([1,2]). We prove that the optimal information rate for each of the six graph access structures is equal to 4/7

DOI
10.4028/www.scientific.net/amr.859.596

Related papers

The Optimal Information Rate of Quantum-Secret-Sharing Schemes Based on at Most Four Participants

Song Yu

The information rate is an important metric of the performance of a quantum-secret-sharing scheme.In this paper,we characterize the quantum access structures by means of the theory of hypergraph.Furthermore,we derive the optimal information rate and the construction of perfect quantum-secret-sharing schemes corresponding to the quantum access structures with at most four players which are given in terms of the relationship between certain access structures and hypergraphs.The exact values for the optimal information rate in 5 of the 13 access structures are computed and the relevant construction of perfect secret sharing schemes is discussed.At the same time,the upper bounds for the information rate of other 8 quantum access structures are computed.

Dianzi xuebao•Jan 1, 2014•1 citation

Optimal Linear Secret Sharing Schemes for Graph Access Structures on Six Participants.

Motahhareh Gharahi, Shahram Khazaei

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.

•Jan 1, 2017•0 citations

A Study On The Average Information Ratio Of Perfect Secret-Sharing Schemes For Access Structures Based On Bipartite Graphs

Hui-Chuan Lu

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.

•Sep 29, 2012•1 citation

NEW METHOD TO COMPUTE BOUNDS ON THE OPTIMAL INFORMATION RATE OF SECRET SHARING SCHEMES

Abbas Cheraghi

In a bipartite secret sharing scheme, the set of participants is divided into two parts, and all participants in each part play an equivalent role. The ideal bipartite access structures were characterized by Padr´o and S´aez, but it is not known which is the optimal information rate of non ideal bipartite access structures. Determining the optimal information rate of general access structures is one of the major problems in secret sharing. We study this open problem restricted to the bipartite access structures, obtaining a new method to compute bounds on the optimal information rate. Namely, by using the connection between secret sharing schemes and polymatroids, we show a linear programming problem that determines, for each access structure, an upper bound on the information rate. Moreover, we show new optimal constructions for certain bipartite access structures.

Facta Universitatis Series Mathematics and Informatics•Nov 21, 2025•0 citations

A New Bound on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based on Bipartite Graphs of Larger Girth

Hui-Chuan Lu

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.

•Jul 5, 2014•0 citations

Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming.

Carles Padró, Leonor Vázquez, Yang An

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.

•Jan 1, 2012•0 citations
The information rate is an important metric of the performance of a secret-sharing scheme. In this paper, we deal with determining the exact values for the optimal information rates of the six graph access structures and improving the information rate of a graph access structure on seven participants, which remained as open problems in Song's and Wang's paper([1,2]). We prove that the optimal information rate for each of the six graph access structures is equal to 4/7
The information rate is an important metric of the performance of a quantum-secret-sharing scheme.In this paper,we characterize the quantum access structures by means of the theory of hypergraph.Furthermore,we derive the optimal information rate and the construction of perfect quantum-secret-sharing schemes corresponding to the quantum access structures with at most four players which are given in terms of the relationship between certain access structures and hypergraphs.The exact values for the optimal information rate in 5 of the 13 access structures are computed and the relevant construction of perfect secret sharing schemes is discussed.At the same time,the upper bounds for the information rate of other 8 quantum access structures are computed.
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.
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 bipartite secret sharing scheme, the set of participants is divided into two parts, and all participants in each part play an equivalent role. The ideal bipartite access structures were characterized by Padr´o and S´aez, but it is not known which is the optimal information rate of non ideal bipartite access structures. Determining the optimal information rate of general access structures is one of the major problems in secret sharing. We study this open problem restricted to the bipartite access structures, obtaining a new method to compute bounds on the optimal information rate. Namely, by using the connection between secret sharing schemes and polymatroids, we show a linear programming problem that determines, for each access structure, an upper bound on the information rate. Moreover, we show new optimal constructions for certain bipartite access structures.
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.
Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.