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

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

Lv yingli, Xiaojun Xu, Zhang Xiao-feng, Lian-Lian Zhang

Published Aug 1, 2012• 0 citations
OpenAlex

Abstract

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.

Related papers

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

Secret sharing schemes and polymatroids

Yang An

Secret sharing, which refers to methods of distributing a secret value among a group of participants, is a very important primitive in cryptology. This thesis contains some contribution to this topic. The results that are presented herein deal with two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares. For both open problems, polymatroids are a powerful tool. On one hand, ideal\n\n\n\nmultipartite secret sharing schemes are strongly connected to polymatroids. On the other hand, the entropies of shares of a scheme determine a polymatroid, and because of that, they are fundamental in the search of lower bounds of the length of the shares. For the first open problem, some new and useful families of ideal multipartite access structures are found by using integer polymatroids. As a result the proofs for the existence of ideal secret sharing schemes for them are simplified in great measure. Regarding the second open problem, we present positive and negative results about the only known technique to find lower bounds: linear programming. The positive result are obtained by strengthening this method. The negative ones show the limitation of this method trying to improve the asymptotic lower bounds.

•Jan 1, 2014•0 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

Unconditionally-secure ideal robust secret sharing schemes for threshold and multilevel access structure

Mahabir Prasad Jhanwar, Reihaneh Safavi–Naini

Abstract. An n -player -secure robust secret sharing scheme is a ( t , n )-threshold secret sharing scheme with the additional property that the secret can be recovered, with probability at least , from the set of all shares even if up to t players provide incorrect shares. The existing constructions of robust secret sharing schemes for the range have the share size larger than the secret size. An important goal in this area is to minimize the share size. In the paper, we propose a new unconditionally-secure robust secret sharing scheme for the case with share size equal to the secret size. This is the minimum possible size as dictated by the perfect secrecy of the scheme. We further extend our scheme to realize a class of multilevel access structures that satisfy a special condition. The property that the share size is equal to secret size is preserved in the extended scheme. The proposed scheme is the first known robust secret sharing scheme realizing multilevel access structure.

Journal of Mathematical Cryptology•Oct 8, 2013•2 citations

General Error Decodable Secret Sharing Scheme and Its Application

Kaoru Kurosawa

Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secretscorrectly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition calledQ3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S| and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).

IEEE Transactions on Information Theory•Sep 1, 2011•8 citations

Not all perfect extrinsic secret sharing schemes are ideal.

W. D. Wallis

Abstract. We construct a perfect extrinsic secret sharing scheme for any case in which a set of participants can gain access to the secret if and only if the set contains a pair of members from some given list of pairs. A secret sharing scheme is a way by which a dealer rnay distribute secret information to individuals (call participants). There is associated '-<U.lh'.lcH"""F- of subsets of a set of can if they constitute a member of the access structure. usual to demand that the access structure be monotone: If A contains a subset which to the structure, then A itself must also belong to the structure. A secret scheme is called perfect if a set of pa.rticipants can no information by their shares unless the set is member of the access structure. An structure is called extrinsic if each participant '8 share contains the same amount of information. Simmons [4] has pointed out the desirability of a scheme which is and the access structure of which extrinsic. Observe

Australas. J Comb.•Jan 1, 1990•0 citations
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‎.
Secret sharing, which refers to methods of distributing a secret value among a group of participants, is a very important primitive in cryptology. This thesis contains some contribution to this topic. The results that are presented herein deal with two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares. For both open problems, polymatroids are a powerful tool. On one hand, ideal\n\n\n\nmultipartite secret sharing schemes are strongly connected to polymatroids. On the other hand, the entropies of shares of a scheme determine a polymatroid, and because of that, they are fundamental in the search of lower bounds of the length of the shares. For the first open problem, some new and useful families of ideal multipartite access structures are found by using integer polymatroids. As a result the proofs for the existence of ideal secret sharing schemes for them are simplified in great measure. Regarding the second open problem, we present positive and negative results about the only known technique to find lower bounds: linear programming. The positive result are obtained by strengthening this method. The negative ones show the limitation of this method trying to improve the asymptotic lower bounds.
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.
Abstract. An n -player -secure robust secret sharing scheme is a ( t , n )-threshold secret sharing scheme with the additional property that the secret can be recovered, with probability at least , from the set of all shares even if up to t players provide incorrect shares. The existing constructions of robust secret sharing schemes for the range have the share size larger than the secret size. An important goal in this area is to minimize the share size. In the paper, we propose a new unconditionally-secure robust secret sharing scheme for the case with share size equal to the secret size. This is the minimum possible size as dictated by the perfect secrecy of the scheme. We further extend our scheme to realize a class of multilevel access structures that satisfy a special condition. The property that the share size is equal to secret size is preserved in the extended scheme. The proposed scheme is the first known robust secret sharing scheme realizing multilevel access structure.
Consider a model of secret sharing schemes with cheaters. We say that a secret sharing scheme is error decodable if we can still recover the secretscorrectly from a noisy share vector (share1', ..., sharen'). In this paper, we first prove that a perfect secret sharing scheme is error decodable if and only if the adversary structure Γ satisfies a certain condition calledQ3. Next, for such Γ , we show a scheme such that the decoding algorithm runs in polynomial-time in |S| and the size of a linear secret sharing scheme which realizes Γ. We finally show an application to 1-round perfectly secure message transmission schemes (PSMT).
Abstract. We construct a perfect extrinsic secret sharing scheme for any case in which a set of participants can gain access to the secret if and only if the set contains a pair of members from some given list of pairs. A secret sharing scheme is a way by which a dealer rnay distribute secret information to individuals (call participants). There is associated '-<U.lh'.lcH"""F- of subsets of a set of can if they constitute a member of the access structure. usual to demand that the access structure be monotone: If A contains a subset which to the structure, then A itself must also belong to the structure. A secret scheme is called perfect if a set of pa.rticipants can no information by their shares unless the set is member of the access structure. An structure is called extrinsic if each participant '8 share contains the same amount of information. Simmons [4] has pointed out the desirability of a scheme which is and the access structure of which extrinsic. Observe