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

SECRET SHARING ON INFINITE GRAPHS

László Csirmaz

Published Jan 1, 2008• 3 citations
OpenAlex

Abstract

We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participantmustrememberforeachbitinthesecret -- justtheinverseoftheinformationrate. Wedeterminethisvalueforseveralin honeycomb lattices; and give upper and finite graphs: lower bounds in on finite path, two-dimensional square and It is also shown that the information ratio is not necessarily the ratio local, for the i.e. triangular all nite spanned lattice. subgraphs have strictly smaller ratio than the whole graph. several open problems.

Related papers

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

Information Ratio of Unicyclic Graphs

Máté Gyarmati

Secret sharing is a method to distribute a secret amongst participants, such that only some predefined coalitions, called qualified sets can recover the secret. The set of the qualified subsets is called the access structure, and if all minimally qualified sets have two elements then the access structure is representable by a graph. The information ratio of an access structure is the amount of information the most overloaded participant must remember per secret bit. In this paper, we compute the information ratio of the unicyclic graph, i.e., connected graphs that are arising from a tree by adding an edge between two non-connected vertices.

IEEE Transactions on Information Theory•Oct 13, 2023•1 citation

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

Online secret sharing

László Csirmaz, Gábor Tardos

First secret sharing with infinitely many participants is looked at, showing that even the threshold cases are non trivial to achieve. We present some interesting infinite ramp shemes supporting the conjecture that all access structure can be realized by some ramp scheme. Secondly we introduce online secret sharing, where the shares should be distributed knowing only the trace of the access structure on the participants seen so far. We show that for graph based access structures the online complexity can be bounded by the graph degree, even in the infinite case.

•Jul 25, 2010•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
We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participantmustrememberforeachbitinthesecret -- justtheinverseoftheinformationrate. Wedeterminethisvalueforseveralin honeycomb lattices; and give upper and finite graphs: lower bounds in on finite path, two-dimensional square and It is also shown that the information ratio is not necessarily the ratio local, for the i.e. triangular all nite spanned lattice. subgraphs have strictly smaller ratio than the whole graph. several open problems.
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 is a method to distribute a secret amongst participants, such that only some predefined coalitions, called qualified sets can recover the secret. The set of the qualified subsets is called the access structure, and if all minimally qualified sets have two elements then the access structure is representable by a graph. The information ratio of an access structure is the amount of information the most overloaded participant must remember per secret bit. In this paper, we compute the information ratio of the unicyclic graph, i.e., connected graphs that are arising from a tree by adding an edge between two non-connected vertices.
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.
First secret sharing with infinitely many participants is looked at, showing that even the threshold cases are non trivial to achieve. We present some interesting infinite ramp shemes supporting the conjecture that all access structure can be realized by some ramp scheme. Secondly we introduce online secret sharing, where the shares should be distributed knowing only the trace of the access structure on the participants seen so far. We show that for graph based access structures the online complexity can be bounded by the graph degree, even in the infinite case.
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.