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

Information Ratio of Unicyclic Graphs

Máté Gyarmati

Published Oct 13, 2023• 1 citation
Publisher

Abstract

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.

DOI
10.1109/tit.2023.3322601

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

SECRET SHARING ON INFINITE GRAPHS

László Csirmaz

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.

•Jan 1, 2008•3 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

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

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
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.
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.
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.
/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.>
‎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‎.
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.