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

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Amos Beimel, Oriol Farràs, Yuval Mintz, Naty Peter

Published Dec 6, 2021• 6 citations
Publisher

Abstract

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph$G=(V,E)$if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in$E$(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with$n$vertices and at most$n^{1+\beta }$edges (resp. at least$\binom {n}{2} - n^{1+\beta }$edges), for some$0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size$\tilde {O} (n^{1+\beta /2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is$\tilde {O} (n^{1/4+\beta /4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size$\Omega (n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is$\Omega (n^{1+\beta /2})$. Finally, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is$\Omega (n^{1/4+\beta /4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

DOI
10.1109/tit.2021.3132917

Related papers

Quadratic Secret Sharing and Conditional Disclosure of Secrets

Amos Beimel, Hussien Othman, Naty Peter

There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes for$n$-party access structures; consistent with our current knowledge the optimal share size can be anywhere between polynomial and exponential in$n$. For linear secret-sharing schemes, the share size for almost all$n$-party access structures is exponential in$n$. We would like to study larger classes of secret-sharing schemes with two goals: 1) prove lower bounds for larger classes of secret-sharing schemes; and 2) construct efficient secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC’20) introduced a new class of secret-sharing schemes in which the shares are generated by applying degree-$d$polynomials to the secret and some random field elements. We define and study two additional classes of polynomial secret-sharing schemes: 1) schemes in which the reconstruction of the secret is done using polynomials; and 2) schemes in which both sharing and reconstruction are done by polynomials. Our main result is a construction of secret-sharing schemes and conditional disclosure of secrets protocols with quadratic sharing and reconstruction that are more efficient than linear secret-sharing schemes. To complement our results, we prove lower bounds on the share size for schemes with polynomial reconstruction. Finally, we give an evidence that schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction.

IEEE Transactions on Information Theory•Jul 18, 2023•3 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

Ideal secret sharing schemes on graph-based 333-homogeneous access structures

Shahrooz Janbaz, Bagher Bagherpour, Ali Zaghian

‎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 $\frac{1}{d+1}$‎. ‎Furthermore‎, ‎we mention three forbidden configurations that are useful in characterizing other families of ideal access structures‎.

•Jun 1, 2021•1 citation

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

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 secret-sharing scheme realizes the forbidden graph access structure determined by a graphG=(V,E)G=(V,E)G=(V,E)if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices inEEE(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph withnnnvertices and at mostn1+βn^{1+\beta }n1+βedges (resp. at least(n2)−n1+β\binom {n}{2} - n^{1+\beta }(2n​)−n1+βedges), for some0≤β<10 \leq \beta < 10≤β<1, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share sizeO~(n1+β/2)\tilde {O} (n^{1+\beta /2})O~(n1+β/2). Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share isO~(n1/4+β/4)\tilde {O} (n^{1/4+\beta /4})O~(n1/4+β/4). We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share sizeΩ(n3/2)\Omega (n^{3/2})Ω(n3/2); this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures isΩ(n1+β/2)\Omega (n^{1+\beta /2})Ω(n1+β/2). Finally, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures isΩ(n1/4+β/4)\Omega (n^{1/4+\beta /4})Ω(n1/4+β/4). This shows that our constructions are optimal (up to poly-logarithmic factors).
There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes fornnn-party access structures; consistent with our current knowledge the optimal share size can be anywhere between polynomial and exponential innnn. For linear secret-sharing schemes, the share size for almost allnnn-party access structures is exponential innnn. We would like to study larger classes of secret-sharing schemes with two goals: 1) prove lower bounds for larger classes of secret-sharing schemes; and 2) construct efficient secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC’20) introduced a new class of secret-sharing schemes in which the shares are generated by applying degree-dddpolynomials to the secret and some random field elements. We define and study two additional classes of polynomial secret-sharing schemes: 1) schemes in which the reconstruction of the secret is done using polynomials; and 2) schemes in which both sharing and reconstruction are done by polynomials. Our main result is a construction of secret-sharing schemes and conditional disclosure of secrets protocols with quadratic sharing and reconstruction that are more efficient than linear secret-sharing schemes. To complement our results, we prove lower bounds on the share size for schemes with polynomial reconstruction. Finally, we give an evidence that schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction.
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.
‎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−3-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−3-3−homogeneous access structures and characterize the ideal graph-based 333-homogeneous access structures‎. ‎We prove that for every non-ideal graph-based 333-homogeneous access structure over the graph GGG with the maximum degree ddd there exists a secret sharing scheme with an information rate 1d+1\frac{1}{d+1}d+11​‎. ‎Furthermore‎, ‎we mention three forbidden configurations that are useful in characterizing other families of ideal access structures‎.
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.
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.