以圖為基礎的存取結構上的祕密分享機制之研究

Abstract

秘密分享機制（secret sharing scheme）是一個將秘密分成許多份（share）分給所有的參與者，使得只有特定被授權的子集（qualified subset）中的人所擁有的shares才可以重新建構出這個秘密;而任意非授權子集中的人，則無法由他們所擁有的shares中找出任何與秘密相關的資訊的一種機制。其中，所有的授權子集所形成的集合我們稱之為該機制的存取結構（access structure）。 所謂以一個圖G為基礎的存取結構，是將圖G上每一個點都視為一個參與者，而任意一個包含某個邊的一些點所成的集合都是一個授權的子集。其中秘密分享機制的訊息比率（information ratio）則是該秘密分享機制下所有參與者所擁有的shares的最大長度與秘密的長度的比值。而我們在這篇論文中所討論圖G的訊息比率（information ratio of G）則是在以圖G為基礎的存取結構中所能造出的所有秘密分享機制的訊息比率的infimum。 在這篇論文中，我們求出了特定無窮圖類的訊息比率的下界，並且利用向量空間的方式，完整造出這特定無窮圖類中兩種特殊子圖類的秘密分享機制，並算出其訊息比率的值皆為$2$。如此便得出這二種子圖類的訊息比率的上界。在某些情形下，此上界與我們推導的下界是相當接近的，亦即我們構造的秘密分享機制是相當好的。

A perfect secret sharing scheme based on a graph G is a randomized distribution of a secret among the vertices of the graph so that the secret can be recovered from the information assigned to the endvertices of any edge, while the total information assigned to an independent set of vertices is independent (in statistical sense) of the secret itself. The (worst case) information ratio of G is the largest lower bound on the amount of information some vertex must remember for each bit of the secret. Using entropy method, we calculate a lower bound on the information ratio for an infinite class of graphs we consider in this thesis. We also use the generalized vector space construction to construct perfect secret sharing schemes with information ratio 2 for two subclasses of graphs. This upper bounded is very close to our lower bound in some circumstances, which means the secret sharing schemes we construct are in fact very good.