以圖為基礎之存取結構上的秘密分享機制的平均訊息比率之研究

Abstract

所謂祕密分享機制(secret-sharing scheme)的概念是一個將秘密(secret)分成許多 shares 給所有參與者(participants)，使得只有授權子集(qualified subset)中的參與者將所分配到的 shares 組合起來才能重建出這個秘密，而非授權子集(nonqualified subset)中的參與者則無法從分配到的shares得到任何有關這個秘密的任何資訊的機制。其中，所有授權子集所成的集合稱為該機制的存取結構(access structure)。一個存取結構中所有最小授權子集所成的集合則稱為該存取結構的基底(basis)。

所謂以圖G為基礎的存取結構是指將圖G中的每個點視為一個參與者而且以圖G的邊集合為基底的存取結構。在秘密分享的問題中被廣為討論的訊息比率(information ratio)與平均訊息比率(average information ratio)則分別定義為參與者所分到的share的最大長度與秘密的長度的比值，以及所有參與者所分到的share的平均長度與秘密的長度的比值。一個存取結構上所能構造出的所有秘密分享機制的(平均)訊息比率的infimum則稱為該存取結構的最佳(平均)訊息比率(optimal (average) information ratio)。在此論文中我們要探討的是以圖為基礎的存取結構的最佳平均訊息比率的問題。

首先我們討論權重門檻型的秘密分享機制。給定一個門檻(threshold) t>0 與一個定義在參與者集合上的權重函數，若一子集中所有參與者的權重和不小於給定的門檻t，則該子集即為一個授權子集。這種授權子集所成的存取結構稱為權重門檻型的存取結構。Morillo等人研究了可以用圖表示的權重門檻型的存取結構並將此種圖稱為一個 k-權重圖(k-weighted graph)。他們清楚刻劃了這種圖的結構並推導了這種存取結構的最佳訊息比率的一個上限。在本論文的第二章中，我們將探討 k-權重圖的最佳平均訊息比率的問題。我們提出兩種秘密分享機制的構造方法並推導它們的平均訊息比率的範圍。兩種構造方式的平均訊息比率都很低，且各有各的優點。當參與者的個數趨近無窮時，我們構造的秘密分享機制的平均訊息比率會趨近於最佳值 1。

由於推導最佳訊息比率與最佳平均訊息比率是相當困難的問題，所以大部分的結果都是提供上下限。在2007年之前被求出最佳訊息比率與最佳平均訊息比率的無窮圖類只有paths和cycles，以及Blundo等人定義出的一種圖類。Csirmaz 與 Tardos 在2007年求出了所有樹圖的最佳訊息比率的正確值。而 Csirmaz 與 Ligeti 則在2009年求得了更廣的圖類的最佳訊息比率正確值。

在本論文的第三章與第四章中，我們則是致力於最佳平均訊息比率的正確值的研究。我們將在論文的第三章提出我們求出以圖為基礎的存取結構的最佳平均訊息比率的正確值的做法。我們的方法將這個秘密分享方面的複雜問題數學模式化為圖論上用簡單語言便能描述的max-min的問題。我們利用這個方法求出所有樹圖的最佳平均訊息比率的正確值，並提供一個有系統的方法求出該值。

而在第四章中，我們更進一步討論二部圖(bipartite graph) 的最佳平均訊息比率的問題。我們求出一個簡單圖的任意 even-subdivision與一些二部圖類的最佳平均訊息比率的正確值。同時，對於尚未被求出最佳平均訊息比率的正確值的二部圖，我們也推導了一個最佳平均訊息比率的上下限。對一些圖類而言，我們的給上下限是用我們的做法可以得到的最佳上下限。

最後在第五章，我們作了簡短的總整理並介紹未來可以繼續努力的研究方向。

A perfect secret-sharing scheme is a method of distributing a secret among a set of n participants in such a way that only qualified subsets of participants can recover the secret and the joint share of the participants in any unqualified subset is statistically independent of the secret. The collection of all qualified subsets is called the access structure of the scheme. In a graph-based access structure, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The information ratio of a perfect secret-sharing scheme realizing a given access structure is the ratio of the maximum length of the share given to a participant to the length of the secret, while the average information ratio is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the (average) information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal (average)information ratio of that access structure. In this thesis, we focus on the average information ratio of graph-based access structures.

In a weighted threshold scheme, each participant has his or her own weight. A subset is qualified if and only if the sum of the weights of participants in the subset is not less than the given threshold. Morillo et al. considered the scheme for a weighted threshold access structure that can be represented by a graph which is referred to as a k-weighted graph. They characterized this kind of access structures and derived a bound on the optimal information ratio. In Chapter 2, we deal with the average information ratio of the secret-sharing schemes for these access structures. Two sophisticated constructions are presented. Bounds on the average information ratio of them are derived. Each of our constructions has its own advantages and both of them perform very well when n/k is large.

Due to the difficulty of finding the exact values of the optimal information ratio and the optimal average information ratio, most results give bounds on them. Before2007, apart from one specially defined class of graphs, the paths and cycles are the only infinite classes of graph-based access structures whose optimal information ratio and optimal average information ratio are known. Csirmaz and Tardos found the exact values of the optimal information ratio of all tree-based access structures in 2007. In 2009, Csirmaz and Ligeti determined the exact values of the optimal information ratio of broader classes of graph-based access structures.

Following in their footsteps, we devote our efforts to the discussion the optimal average information ratio of tree-based access structures in Chapter 3. We successfully determine the exact values of the optimal average information ratio of all tree-based access structures. Our idea also formulates a complicated problem in secret-sharing into a problem in Graph Theory with easy description.

Extending our work in Chapter 3, we are dedicated to the study the optimal average information ratio of the access structures based on bipartite graphs in Chapter 4. We determine the optimal average information ratio of some classes of bipartite graphs. In addition, we also give a bound on the optimal average information ratio of the rest classes of bipartite graphs. This bound is the best for some classes of bipartite graphs using our approach.

In the final chapter, we summarize our work in this thesis and introduce possible directions of future research.