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

arXiv:2608.17047

Secret Sharing at the Shannon Ceiling

Christopher Williamson

Published Aug 17, 2026• 0 citations
arXivHTMLPDF

Abstract

For every $n\geq 9$ that is a multiple of 3, we construct an explicit access structure on $n$ participants. In every perfect secret-sharing scheme realising this access structure, if $S$ denotes the random secret, then the sum of the share entropies is at least $\left(\frac{n^2}{9}+\frac{2n}{3}\right)H(S)$, and some participant has share entropy at least $\left(\frac{n}{6}+\frac12\right)H(S)$. After normalisation by $H(S)$, these are respectively $Ω(n^2)$ and $Ω(n)$ lower bounds and also give the same asymptotic lower bounds on the total and largest expected binary lengths of the shares. This improves by a logarithmic factor the longstanding general lower bounds of $Ω(n^2/\log n)$ for total share size and $Ω(n/\log n)$ for maximum share size due to Csirmaz. The proof uses only elementary Shannon inequalities, together with some averaging arguments. The Shannon-information method has universal $O(n^2)$ and $O(n)$ ceilings for the total and maximum normalised entropy lower bounds it can certify, so our construction reaches both ceilings up to constant factors.

DOI
10.48550/arxiv.2608.17047

Related papers

On the Size of a Share for Non-perfect Secret Sharing Schemes

Maki Yoshida

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 $\frac{{{2^k} - 1}}{k} \cdot 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 $\frac{1}{L}$ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of $\frac{{{2^k} - 1}}{{kL}} \cdot H(s)$, under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely $\frac{{{2^k} - 2 + 1/L}}{k} \cdot 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.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations

Secret Sharing and Non-Shannon Information Inequalities

Amos Beimel, Ilan Orlov

The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2O(n), wherenis the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz, who proved that there exist access structures withnparticipants such that the size of the share of at least one party isn/logntimes the secret size. Csirmaz's proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω(n) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. In fact, it was proved that there are infinity many independent information inequalities even in four variables. This raises the hope that these inequalities can help in improving the lower bounds beyondn. However, we show that any information inequality with four or five variables cannot prove a lower bound of ω(n) on the share size. In addition, we show that the same negative result holds for all information inequalities with more than five variables that are known to date.

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

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

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

Secret sharing schemes based on min-entropies

Mitsugu Iwamoto, Junji Shikata

Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.

arXiv:1401.5896•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•8 citations
For every n≥9n\geq 9n≥9 that is a multiple of 3, we construct an explicit access structure on nnn participants. In every perfect secret-sharing scheme realising this access structure, if SSS denotes the random secret, then the sum of the share entropies is at least (n29+2n3)H(S)\left(\frac{n^2}{9}+\frac{2n}{3}\right)H(S)(9n2​+32n​)H(S), and some participant has share entropy at least (n6+12)H(S)\left(\frac{n}{6}+\frac12\right)H(S)(6n​+21​)H(S). After normalisation by H(S)H(S)H(S), these are respectively Ω(n2)Ω(n^2)Ω(n2) and Ω(n)Ω(n)Ω(n) lower bounds and also give the same asymptotic lower bounds on the total and largest expected binary lengths of the shares. This improves by a logarithmic factor the longstanding general lower bounds of Ω(n2/log⁡n)Ω(n^2/\log n)Ω(n2/logn) for total share size and Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) for maximum share size due to Csirmaz. The proof uses only elementary Shannon inequalities, together with some averaging arguments. The Shannon-information method has universal O(n2)O(n^2)O(n2) and O(n)O(n)O(n) ceilings for the total and maximum normalised entropy lower bounds it can certify, so our construction reaches both ceilings up to constant factors.
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 2k−1k⋅H(s)\frac{{{2^k} - 1}}{k} \cdot H(s)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 1L\frac{1}{L}L1​ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of 2k−1kL⋅H(s)\frac{{{2^k} - 1}}{{kL}} \cdot H(s)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 2k−2+1/Lk⋅H(s)\frac{{{2^k} - 2 + 1/L}}{k} \cdot H(s)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 known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2O(n), wherenis the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz, who proved that there exist access structures withnparticipants such that the size of the share of at least one party isn/logntimes the secret size. Csirmaz's proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω(n) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. In fact, it was proved that there are infinity many independent information inequalities even in four variables. This raises the hope that these inequalities can help in improving the lower bounds beyondn. However, we show that any information inequality with four or five variables cannot prove a lower bound of ω(n) on the share size. In addition, we show that the same negative result holds for all information inequalities with more than five variables that are known to date.
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.
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.
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.
Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.