【作者】 许静芳；

【导师】 崔国华；

【作者基本信息】 华中科技大学 ， 信息安全， 2010， 博士

【摘要】 随着信息安全技术发展和应用的日益广泛,秘密共享方案被越来越多地应用于各种安全协议中。在秘密共享方案中,理想的秘密共享方案的效率是最优的,它实现的存取结构称为理想的存取结构。但并不是所有的存取结构都存在实现该结构的理想的秘密共享方案,即为非理想的存取结构,理想的存取结构的特征描述是秘密共享领域中的一个急待解决的困难问题。由于与可表示的拟阵相关联的存取结构均为理想的,拟阵论是解决这一问题的重要途径,大量的研究工作围绕着这一主题而展开,即运用拟阵论的知识寻找理想的存取结构的特征进而运用该特征为具体的存取结构构造理想的秘密共享方案。针对每个拟阵和存取结构都是多部的这一特点以及多部拟阵与离散多拟阵之间的密切联系,从离散多拟阵的基集合以及秩函数等多个角度出发,分别研究和证明了可表示的以及不可表示的多部拟阵所满足的多个充分或者必要条件,研究的目的旨在通过这些充分或者必要条件进一步得到多部存取结构为理想的充分或者必要条件。随后,通过将这些结论应用于两类具体的存取结构,门限的存取结构和基于图的连通性的存取结构,分别构造了一个理想的门限秘密共享新个体加入协议和一个理想的基于图的连通性的多密钥共享方案。多部拟阵的可表示性可通过离散多拟阵的可表示性来完全描述,并且秩函数可完全确定一个离散多拟阵,通过处理离散多拟阵的秩函数,定义了一类特殊的离散多拟阵,缩减的离散多拟阵,使得多个离散多拟阵对应一个缩减的离散多拟阵,证明了可表示的缩减离散多拟阵能够完全描述可表示的离散多拟阵,进而得到多部存取结构为理想的一个新的充分条件。通过将这一结论应用于m部拟阵(m≤3),于是产生了与一部,二部以及三部拟阵相关联的所有存取结构均为理想的这一结论的一个新的证明方法。该证明方法可进一步推广到研究四部可表示的拟阵的特征。每个多部拟阵都有一个与其对应的离散多拟阵,且基集合可唯一确定一个离散多拟阵。通过研究离散多拟阵的基集合的特性,得到了一个向量集合是离散多拟阵的基集合的必要条件,由此推导出多部存取结构为理想的一个必要条件。因此,分别描述了二部、三部以及四部拟阵的基集合的特征,相应地,由这些特征可分别导出与二部、三部以及四部拟阵相关联的存取结构为理想的必要条件。通过引入离散多拟阵的R集合的概念,证明得到多部拟阵为可表示的一个新的充分条件,由该条件可导出存取结构为理想的一个新的充分条件。运用这一结论,容易得到所有与一部,二部及三部拟阵相关联的存取结构均为理想的,进一步地,通过对四部的D缩减离散多拟阵的R集合进行操作,最终得到四部可表示拟阵特征的完全描述,解决了四部可表示拟阵的特征描述这一迄今为止尚未解决的问题。根据多部拟阵与离散多拟阵之间的对应关系以及秩函数可完全确定一个离散多拟阵这一特性,通过对离散多拟阵秩函数上的操作,建立了一套新的符号系统,利用该符号系统得到并证明了多部拟阵为不可表示的一个新的必要条件,并将这一结论分别应用于m部拟阵(m≤2)和Vamos拟阵,通过实例验证了该结论的实用性和计算的便捷性。Vamos拟阵是第一个被证明为不可表示的拟阵,与其相关联的存取结构均为非理想的。针对Vamos拟阵并利用向量的线性相关和线性无关性给出了Vamos拟阵为不可表示的一个新的证明方法。通过该证明方法由Vamos拟阵引出一系列多部拟阵,得到了一族不可表示的多部拟阵,即Vamos家族。将这一结论推广到一般情况,进而得到一类不可表示的多部拟阵,即推出了多部拟阵为不可表示的一个新的充分条件。门限秘密共享方案实现的存取结构实质上是一部的存取结构,通过产生的理想的存取结构的特征论证了门限秘密共享方案实现的存取结构均为理想的。针对门限方案中需要有一种高效安全的方案为新个体产生并分配子秘密,设计了一个理想的秘密共享新个体加入协议,协议构造过程中针对已有的Dong协议给出了2种攻击,使得不良的广播接收者可以很容易的恢复出t个旧成员的子秘密、新个体的子秘密以及主秘密,论证了导致这2种攻击成功的根本原因。进而构造出了一个新的理想的门限秘密共享新个体加入协议,新协议不仅弥补了原方案的安全缺陷,而且与已有的协议相比减少了通信开销。根据得到的理想的存取结构的特征,通过构造与该结构相关联的拟阵的表示法,对一类基于图的连通性的多存取结构设计了一个实现该结构的多密钥共享体制,与已有的直和方法相比,该体制中每个成员所管理的子密钥的长度都等于主密钥的长度,即为理想的多秘密共享方案。利用最优线性多密钥共享体制的相关理论证明了该体制是一个最优线性多密钥共享体制,同时证明了该体制的正确性和安全性,即每一个主密钥所对应的存取结构的子集可以重构该主密钥,不是该存取结构的子集不能获取对应主密钥的任何信息。更多还原

【Abstract】 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.更多还原