Research On Ideal Access Structures And Schemes Constructions In Secret Sharing

With the widespread application and development of information security technology, secret sharing schemes have been widely applied for a variety of cryptography procotols, in which ideal secret sharing schemes have optimal efficiency. The structures realized by ideal secret sharing schemes are called ideal access structures. Not all access structures are ideal since there does not exist an ideal secret sharing scheme realizing it, namely, they are non-ideal access structures. Thus, the characterization of ideal access structures is a longstanding open problem in secret sharing, which has interesting connection to martoid theory since all access structures induced by representable matroids are ideal. By using the well known connection between ideal secret sharing and matroids, several researchers study the characterization of ideal access structures and further construct ideal secret sharing schemes for particular families of access structures.Due to the fact that every access structure and matroid are multipartite, by using the connection between multipartite matroids and discrete polymatroids, we study the bases and the rank functions of discrete polymatroids. As a result, we obtain multiple sufficient or necessary conditions for a multipartite matroid to be representable or non-representable, which imply multiple sufficient or necessary conditions for an access structure to be ideal. Subsequently, by applyng these conclusions for two particular families of access structures, we build an ideal threshold secret sharing protocol for member expansion and an ideal multi-secret sharing scheme based on connectivity of graphs respectively.Since the representability of a muliparite matroid can be completely characterized by the representability of the associated discrete polymatroid which is completely determined by its rank function, by dealing the rank functions of discrete polymatroids, we define D-reduction discrete polymatroids such that multiple discrete polymatroids correspond to a D-reduction discrete polymatroid, and further prove that the representability of a discrete polymatroid can be completely characterized by the representability of the associated discrete polymatroid reduction, which implies a new sufficient condition for an access structure to be ideal. By using this sufficient condition, we give a new proof that all access structures related to m-partite matroid (m≤3) are ideal, which can be extended to study the case of m=4.Every muliparite matroid has an associated discrete polymatroid, which can be uniquely determined by its bases, by studying the properties of the bases of discrete polymatroids, we obtain a necessary condition for a set of vectors to be the bases of a discrete polymatroid, which implies a necessary condition for a multipartite access structure to be ideal. Concretely, we describe the properties of the bases of bipartite, tripartite and quadripartite matroids respectively, which show the necessary conditions for multipartite access structures induced by bipartite, tripartite and quadripartite matroids to be ideal accordingly.By introducing the concept on the R-set of a discrete polymatroid, we provide a new and simple sufficient condition for a multipartite matroid to be representable, which implies a sufficient condition for an access structure to be ideal. By using this sufficient condition, we easily obtain that every access structure related to m-partite matroid (m≤3) is ideal, which generalizes previous results on ideal access structures related to m-partite matroid (m≤3). Further, we present a complete characterization of quadripartite representable matroids, which was until now an open problem, and hence, all access structures related to quadripartite representable matroids are the ideal ones.Since every muliparite matroid has an associated discrete polymatroid, which is completely determined by its rank function, by dealing the rank functions of discrete polymatroids, we define a new symbol system, by which a necessary condition for a multipartite matroid to be non-representable is obtained. When we apply this necessary condition to m-partite matroid (m<2) and Vamos matroid, the practicability and convenience of computations are verified.Vamos matroid was firstly proved to be non-representable and all access structures induced by it are non-ideal. Using the linearly dependent and independent vectors, we give a new proof method that the Vamos matroid is a non-representable multipartite matroid, by which we deal with a family of matroids derived from the Vamos matroid and hence, a family of non-representable matroids is obtained, that is, Vamos Family. When we extend this conclusion to the general cases, a sufficient condition for a multipartite matroid to be non-representable is provided.Access structures realized by threshold secret shaing schemes are actually unipartite ones. By using the conclusions of the above, we easily obtain that threshold access structures are ideal. In order to build a efficient and secure threshold secret sharing protocol for member expansion, we firstly study the existing Dong protocol and give two attacks such that a malicious broadcast receiver may easily recover old t shares, new share and further reconstruct the secret. Further, a new protocol is proposed, which elaborately eliminates the defect of Dong protocol and improves the efficiency of previous schemes.According to the obtained conclusions of the above, we construct a representation of the matroid related to a family of access structures based on the connectivity of graphs and hence, an ideal linear multi-secret sharing scheme based on connectivity of graphs is proposed. It is proved that this multi-secret sharing scheme satisfy both the reconstruction property and the secure property of the perfect secret sharing scheme. By using the concept of optimal linear multi-secret sharing scheme, we analyze the complexity of this scheme and draw a conclusion that this linear multi-secret sharing scheme is an optimal linear multi-secret sharing scheme.