完美多重機密配置系統問題

機密配置系統(secret sharing scheme)最早在1979年分別由Shamir及Blakely提出。透過此系統, 合法參與者可依據不同權限所分配到有關於此機密(secret) 的一些片段(shares) 來重建此機密, 不合法的參與者則無法得到任何有關於此機密的資訊。我們稱所有合法的參與者子集合所形成的集合為授權者集合(access structure), 而所有不合法的參與者子集合所形成的集合為拒絕集集合(prohibited structure)。多重機密配置系統是機密配置系統的一個延伸, 表示可同時處理多個機密。一般而言, 最大改善率(maximum improvement ratio) 及平均改善率(average improve-ment ratio) 為衡量一個多重機密配置系統好壞的依據。此篇論文可分為三大部份。第一部份, 針對一般超圖(general hypergraph) 的拒絕集, 我們提出了一個完美機密配置系統, 此系統能處理一般化的MSSS 問題, 並且不需要公佈任何資訊。第二部份, 對於2003年Crescenzo 所提出的最大改善率以及平均改善率之最佳猜測值, 我們提出了一個創新的多重機密配置系統, 用以證明此兩大最佳改善率可同時被達到。第三部份, 對於2006年Pang 等學者所提出之多重機密配置系統, 我們提出了兩個改進的多重機密配置系統(GMS1, GMS2), 分別在時間複雜度和公佈資訊量上勝於Pang 等學者所提出的系統。同時,GMS1更達到了弱完美(weak-perfect) 的性質。另外, 本篇論文所提出之機密配置系統皆增設了可驗證、偵測以及多次使用之功能。

關鍵字

資訊安全；機密配置；多重機密；超圖；拒絕集集合；改善率

並列摘要

Secret sharing was invented by Adi Shamir and George Blakely independently in 1979. A secret sharing scheme (SSS) includes two efficient algorithms(D, R). Formally, given a group of participants P = {P1, P2, · · · , Pn}. Distribution algorithm D is executed by a dealer who was given a secret, computes some shares (shared key) Si and distributes them to each participant Pi. Reconstruc- tion algorithm R is executed by authorized subsets of participants who combine their own shares will reconstruct the secret. A subset A of P is called a qualified subset and a secret can be reconstructed if every participant in A uses his (or her) own shares and executes the reconstruction algorithm R.Γ⊆ 2P is called an access structure which is the set of all qualified subsets.△⊆ 2P is called a prohibited structure which is the set of all non-qualified subsets. A multi-secret sharing scheme (MSSS) is an extension of a single secret sharing scheme in which many secrets are distributed together. In general, max-improvement ratio (MaxIR) and average-improvement ratio (AvIR) are the quan- tities that measure how well a MSSS performs. We divide this thesis into three parts. In first part, we propose a perfect secret sharing scheme for prohibited structures based on general hypergraph. This scheme has no public information and includes Weng’s scheme as a special case. In second part, we prove that both optimal improvement ratios of a multi-secret sharing scheme can be achieved at the same time. In third part, we propose two optimal multi-secret sharing schemes with general access structures. These two schemes are more secure and efficient than PLW scheme respectively and also achieve both optimal maximum improvement ratio and optimal average improvement ratio.