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 International Symposium on Information Theory (ISIT)

On the information rate of perfect secret sharing schemes

Marten van Dijk

Published Dec 17, 2002• 2 citations
Publisher

Abstract

We present a method to derive information theoretical upper bounds on the information rate and average information rate of perfect secret sharing schemes. One of the applications is that in perfect secret sharing schemes for some access structures the shares need to be impractically large.>
DOI
10.1109/isit.1994.395104

Related papers

Bounds on the information rate of quantum-secret-sharing schemes

Pradeep Kiran Sarvepalli

An important metric of the performance of a quantum-secret-sharing scheme is its information rate. Beyond the fact that the information rate is upper-bounded by one, very little is known in terms of bounds on the information rate of quantum-secret-sharing schemes. Furthermore, not every scheme can be realized with rate one. In this paper we derive upper bounds for the information rates of quantum-secret-sharing schemes. We show that there exist quantum access structures on $n$ players for which the information rate cannot be better than $O((\mathrm{log}{}_{2}n)/n)$. These results are the quantum analogues of the bounds for classical-secret-sharing schemes proved by Csirmaz.

arXiv:1007.1232•Physical Review A•Apr 21, 2011•4 citations

New bounds on the information rate of secret sharing schemes

Carlo Blundo, Alfredo De Santis, Antonio Giorgio Gaggia +1 more

/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>

IEEE Transactions on Information Theory•Mar 1, 1995•30 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

Upper and lower bounds for secret sharing schemes with general access structures

Sofia Barbetta

Secret sharing schemes are a fundamental cryptographic tool for securely distributing sensitive information among multiple parties according to a specified access structure. For a given access policy, several schemes with different levels of efficiency may exist. One of the main parameters in this analysis is the share size and a central goal is to minimize it. This thesis studies the complexity of secret sharing schemes by focusing on lower and upper bounds on the share size for arbitrary and explicit access structures. The main objective is to collect the most relevant results in the literature, ranging from early lower bounds due to Karnin et al. and Csirmaz and upper-bound of Liu and Vaikuntanathan to recent advances that have significantly improved known bounds. Despite this progress, a significant gap between lower and upper bounds remains, leaving the determination of the optimal share size an open problem.

•Jan 27, 2026•0 citations

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
An important metric of the performance of a quantum-secret-sharing scheme is its information rate. Beyond the fact that the information rate is upper-bounded by one, very little is known in terms of bounds on the information rate of quantum-secret-sharing schemes. Furthermore, not every scheme can be realized with rate one. In this paper we derive upper bounds for the information rates of quantum-secret-sharing schemes. We show that there exist quantum access structures on nnn players for which the information rate cannot be better than O((log2n)/n)O((\mathrm{log}{}_{2}n)/n)O((log2​n)/n). These results are the quantum analogues of the bounds for classical-secret-sharing schemes proved by Csirmaz.
/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>
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 schemes are a fundamental cryptographic tool for securely distributing sensitive information among multiple parties according to a specified access structure. For a given access policy, several schemes with different levels of efficiency may exist. One of the main parameters in this analysis is the share size and a central goal is to minimize it. This thesis studies the complexity of secret sharing schemes by focusing on lower and upper bounds on the share size for arbitrary and explicit access structures. The main objective is to collect the most relevant results in the literature, ranging from early lower bounds due to Karnin et al. and Csirmaz and upper-bound of Liu and Vaikuntanathan to recent advances that have significantly improved known bounds. Despite this progress, a significant gap between lower and upper bounds remains, leaving the determination of the optimal share size an open problem.
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.