论文标题:拟阵与秘密共享体制
Secret Sharing Schemes—Constructions,Impementations and Information Rate
论文作者 黄根勋
论文导师 张利民,论文学位 博士,论文专业 密码学
论文单位 解放军信息工程大学,点击次数 469,论文页数 57页File Size1906k
2001-05-01论文网 http://www.lw23.com/lunwen_477648082/ 拟阵,秘密共享体制,多密,拟阵的表示,欺骗攻击,搜索攻击
matroid, secret sharing schemes, multi-secret, representation of a matroid, attack by cheating, attack by searching
拟阵理论在组合优化、整数规划、网络流及电网络理论中有了广泛的应用，近十年人们又注意到拟阵与秘密共享体制之间的内在联系，做出了不少很优秀的工作。本文讨论了拟阵与秘密共享体制之间的关系，并利用拟阵作为工具，研究得到了一些具有诸多优点的秘密共享体制，及其构造方法。 本文共分六章，其结构如下： （1）第一章引言部分，简要介绍了拟阵的起源，以及秘密共享体制的近期研 究动向。 （2）第二章介绍了有关拟阵的一些最基本的概念，以及秘密共享体制的基本 概念，其中秘密共享体制的定义略显复杂，是由于考虑到本文中将要讨 论单密与多密、完备与非完备等多种形式的体制，作者希望有一个能够 统一的表示。 （3）第三章的第一节，主要介绍了前人所做的有关工作，其中多数结果在本 文中未给出证明，以免显得过于繁杂；而少数结果在文中给出了简要证 明，以尽可能的有助于读者理解不同概念之间的关系。在第二节，作者 讨论了基于网络流上的单密共享体制，得知对任意网络N，均可构造一 理想的单密共享体制，使其极小通道结构对应于网络N的极小割集族， 且对每一密钥的子密钥一个分配法则恰为网络N上的一个流。而构造此 类单密共享体制的关键是，找到与网络N相关联的有向图G的基本圈矩 阵B，很有效地找到了图G的割拟阵T（G）的一个线性表示。 （4）第四章主要讨论了理想的多密共享体制的存在性问题，并得到一种构造 方法。 在第一节中，作者给出了一个必要性定理，和一个充分性定理。两 个定理中的条件都是针对拟阵而提出的，因而也是直接针对相关的通道 结构集族的，使之具有更强的可操作性。 在第二节中，作者利用二元拟阵的线性表示在本质上具有唯一性， 得到了F_2上理想的多密共享体制存在的一个充分必要条件。并且得到 利用可表示的拟阵，来构造理想的多密共享体制的一个可行办法。 在第三节中，作者给出了理想的多密门限体制存在的一个充分必要 条件。得知，一个理想的多密门限体制，其内部各个通道结构之间存在 着极强的制约关系。因此要想实现具有多种变化的通道结构的理想的多 密门限体制，其能变化的程度也很有限。指出了另一类理想的多密共享 体制的存在性，这一类体制与理想的多密门限体制略有不同。 （5）秘密共享体制的基本想法很有实际意义，要想广泛地将之付诸实践，尚 有不少的技术性问题需要解决，如何防止欺骗攻击和搜索攻击就是其中 比较突出的两个。第五章讨论了两种具有抗攻击能力的秘密共享体制， 给出了由理想的多密共享体制来构造所需要的体制的有效方法。
The Wid theory has found its aPplication in the fields of combinatoryoPtindZation, integral programrning, network fiows and electronic network. In thelast l0 yeas, it is discovered that close connection between the theory of matIOidand the concept of secret shallng schemes. And a lot of excellent work is doneever since. In this paPer the author discusses the relationship betWeen the matroidand secret sharing schemes. He gets some secret sharing schemes with desiredProperties, by takng a matroid as a tool. And he presenis a method to conStructthem.There are six chapters in this paper. The sboe of it is as following.(l) 1n ChaPter 1, it is briefly intrOduced the origin of the matroid theory aswell as the current researching of secret sharing schemes.(2) In ChaPter 2, it is introduced some basic notations of the matroid, and thatof secret sharing schemes.(3) In the first section of ChaPter 3, it is presented some previous studies aboutthe matrOid and the schemes. In the second section, the authOr discussesthe ideal secret sharing schemes based on the network. It comes to aconclusion, that is, "For a given netWork, an ideal secret sharing schemecan be construted, such tha its minimal access sbefore is just the sst ofall the minimal cuts of the given netWork." The key of the constnJcting isthat an efficient represetalion of the cut matroid of an oriented graPh isround.(4)ChaPter 4 mainly discusses the existence of ideal muti-secret sharingschems, and gives a method tO constnJct them.lI In the first section of it, the author presents two theorems. One of it is about the necessary conditions, the other is about the sufficient conditions. And the conditions in the theorems are related with the matroids concerned, so they are directly related to the access structures. It is practical. In the second section, the author presents a theorem of necessity and sufficient conditions for the existence of a binary ideal multi-secret sharing scheme. In the third section, it is proposed a theorem of necessary and sufficient conditions for the existence of an ideal multi-secret threshold scheme. The strong restriction between the access structures is proposed. The author shows the existence of a class of ideal multi-secret sharing schemes slightly different from the threshold schemes.(5) In Chapter 5, the secret sharing schemes, which are able to prevent some attacks, are discussed. A method is showed to construct such schemes.
|
