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:1308.3763 · Journal of Mathematical Cryptology

A characterisation of ideal weighted secret sharing schemes

Ali M. Hameed, Arkadii M. Slinko

Published Oct 6, 2015• 5 citations
arXivHTMLPDF

Abstract

Abstract Beimel, Tassa and Weinreb [SIAM J. Discrete Math. 22 (2008), 360–397] and Farràs and Padró [Lecture Notes in Comput. Sci. 5978, Springer, 2010, 219–236] partially characterised access structures of ideal weighted secret sharing schemes in terms of the operation of composition. They proved that any weighted ideal access structure is a composition of indecomposable ones. Farràs and Padró gave a list of seven classes of access structures – one unipartite, three bipartite and three tripartite – to which all weighted ideal indecomposable access structures may belong. In this paper we determine exactly which access structures from those classes are indecomposable. We also determine which compositions of indecomposable weighted access structures are again weighted and obtain an if-and-only-if characterisation of ideal weighted secret sharing schemes. We use game-theoretic techniques to achieve this.

DOI
10.1515/jmc-2015-0002

Related papers

Ideal Hierarchical Secret Sharing Schemes

Oriol Farràs, Carles Padró

Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well-known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.

IEEE Transactions on Information Theory•Jan 25, 2012•67 citations

Secret sharing schemes with bipartite access structure

G. Sáez, Carles Padró

We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights.

IEEE Transactions on Information Theory•Jan 1, 2000•113 citations

On ideal and weakly-ideal access structures

Reza Kaboli, Shahram Khazaei, Maghsoud Parviz

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.

Advances in Mathematics of Communications•Jun 11, 2021•2 citations

Universally ideal secret-sharing schemes

Amos Beimel, Benny Chor

Given a set of parties {1, /spl middot//spl middot//spl middot/, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions.>

IEEE Transactions on Information Theory•May 1, 1994•113 citations

Ideal and perfect multi-secret sharing schemes whose access structure are Q 3

Lv yingli, Xiaojun Xu, Zhang Xiao-feng +1 more

The characterization of access structure is one of the main open problems in secret sharing schemes. We are particularly interested in determining which Q 3 access structures can be realized and the requirement should be achieved even in the presence of an adversary who is able to corrupt some players in an ideal secret sharing scheme. The problems are studied in our paper. Above all, we present a concrete scheme that can meet all above requirements. In our scheme, it is not only a dynamic multi-secret and multi-use sharing protocol, but participants from access structure can recover the secret using their shares, while the same number of participants from adversary structure can't recover the secret using their shares, which is different from general access structure schemes. Moreover, in the whole dynamic process, the coefficients of polynomial and private secret shares always stay the same. Therefore, it enjoys high practical value.

•Aug 1, 2012•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
Abstract Beimel, Tassa and Weinreb [SIAM J. Discrete Math. 22 (2008), 360–397] and Farràs and Padró [Lecture Notes in Comput. Sci. 5978, Springer, 2010, 219–236] partially characterised access structures of ideal weighted secret sharing schemes in terms of the operation of composition. They proved that any weighted ideal access structure is a composition of indecomposable ones. Farràs and Padró gave a list of seven classes of access structures – one unipartite, three bipartite and three tripartite – to which all weighted ideal indecomposable access structures may belong. In this paper we determine exactly which access structures from those classes are indecomposable. We also determine which compositions of indecomposable weighted access structures are again weighted and obtain an if-and-only-if characterisation of ideal weighted secret sharing schemes. We use game-theoretic techniques to achieve this.
Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well-known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.
We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights.
For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.
Given a set of parties {1, /spl middot//spl middot//spl middot/, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions.>
The characterization of access structure is one of the main open problems in secret sharing schemes. We are particularly interested in determining which Q 3 access structures can be realized and the requirement should be achieved even in the presence of an adversary who is able to corrupt some players in an ideal secret sharing scheme. The problems are studied in our paper. Above all, we present a concrete scheme that can meet all above requirements. In our scheme, it is not only a dynamic multi-secret and multi-use sharing protocol, but participants from access structure can recover the secret using their shares, while the same number of participants from adversary structure can't recover the secret using their shares, which is different from general access structure schemes. Moreover, in the whole dynamic process, the coefficients of polynomial and private secret shares always stay the same. Therefore, it enjoys high practical value.
‎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‎.