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

IEEE Transactions on Information Theory

Secret sharing schemes with bipartite access structure

G. Sáez, Carles Padró

Published Jan 1, 2000• 118 citations
Publisher

Abstract

We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights.

DOI
10.1109/18.887867

Related papers

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 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

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

Secret sharing schemes on access structures with intersection number equal to one.

Jaume Martí-Farré, Carles Padró

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.

•Jan 1, 2002•0 citations

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

Ideal Hierarchical Secret Sharing Schemes

Oriol Farràs, Carles Padró

Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well-known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.

IEEE Transactions on Information Theory•Jan 25, 2012•69 citations
We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights.
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.
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.
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.
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.
Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well-known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.