利用超圖所設計之對於一般授權者集合的完美機密配置系統

機密配置系統 (secret sharing scheme) 是一種使一群參與者可以共同分享一個機密(secret)的系統。透過此機制，參與者可依據不同的權限分配到有關此機密的一些片段(share)。所謂的完美機密配置系統則表示：在此系統中，合法的參與者子集合可以透過拿出各自分到的片段來重建回這個機密；不合法的參與者集合則無法得到任何有關機密的資訊。我們稱所有合法的參與者子集合之集合為授權者集合 (access structure)。在超圖 (hypergraph) 中，如果所有邊都是由r個點所組成，即邊的大小均為 $r$，我們將此圖形稱為 $r$ 一致超圖 ($r$-uniform hypergraph)，而基於 $r$ 一致超圖的授權者集合，則表示可以使用一個$r$一致超圖來表示的授權者集合。意即，給定一超圖，當 $r$ 個點形成一個邊時，即表此 $r$ 個參與者可以重建回機密。同理，($r_1, r_2$)一致超圖則表示圖形上的邊大小均為 $r_1$或 $r_2$，以此種圖形表示的授權者集合則稱為基於($r_1, r_2$)一致超圖(($r_1, r_2$)-uniform hypergraph-based)的授權者集合。依此類推，($r_1, r_2, r_3$)一致超圖則表示圖形上的邊，大小均為 $r_1$、$r_2$或 $r_3$，以此種圖形表示的授權者集合則稱為基於($r_1, r_2, r_3$)一致超圖(($r_1, r_2, r_3$)-uniform hypergraph-based)的授權者集合。依照這樣的想法延伸，當邊的大小不再限制種類多寡時，所對應之授權者集合即成為可任意選取的一般授權者集合（general access structure）。在此篇論文中，我們分別對基於$r$一致超圖、($r_1, r_2$)一致超圖、($r_1, r_2, r_3$)一致超圖以及一般化超圖之授權者集合分別提出相對的完美機密配置系統。並且，對基於一般授權者集合的完美機密配置系統做改進：一、加入驗證片段及偵測欺騙者的功能。二、多次使用功能(使其系統所分配之片段可重複使用)。三、可驗證片段及偵測欺騙者的可多次使用之機密配置系統。

關鍵字

機密配置系統；超圖；授權者集合；驗證及偵測；多次使用

並列摘要

A secret sharing scheme is a method to distribute a secret, also called master key, among a set of participants, such that only qualified subsets of the participants can recover the secret. A secret sharing scheme is perfect if any unqualified subset obtains no information regarding the master key. The collection of qualified subsets is called the access structure. In a hypergraph, if the size of any edge is equal to $r$, the hypergraph is called an $r$-uniform hypergraph. Similarity, if the size of any edge is equal to either $r_1$ or $r_2$ in a hypergraph, the hypergraph is called an ($r_1, r_2$)-uniform hypergraph. And, if the possible size of any edge is $r_1, r_2$ or $r_3$ in a hypergraph, the hypergraph is called an ($r_1, r_2, r_3$)-uniform hypergraph. Given any hypergraph $G$, a $G$-based access structure is an access structure which using $G$ present the access structure, where a vertex denote a participant and the edge set denote the minimal access structure of a secret sharing scheme. In this thesis, we propose four perfect secret sharing schemes for $r$-uniform, ($r_1, r_2$)-uniform, ($r_1, r_2, r_3$)-uniform and general hypergraph-based access structures (called $r$-HA, ($r_1, r_2$)-HA, ($r_1, r_2, r_3$)-HA and G-HA scheme respectively). Moreover, we modify G-HA scheme such that it: 1. can verify the shares (verification) and detect the cheater (detection), 2. can be reused, that is, will be multi-use secret sharing scheme, and 3. will be a multi-use secret sharing scheme with verification and detection. At last, this thesis shows that $r$-HA, ($r_1, r_2$)-HA, ($r_1, r_2, r_3$)-HA and G-HA schemes are all more efficient secret sharing scheme than the scheme be hold by Tochikubo, Uyematsu and Matsumoto in 2005 for the respective same access structure.

並列關鍵字

secret sharing scheme ； hypergraph ； access structure ； verification and detection ； multi-use

參考文獻

[1] J Benaloh and J Leichter, “Generalized secret sharing and monotone functions,” Proceeding of CRYPTO’88, pp 27–35, 1998

Google Scholar

[2] G R Blakley, “Safeguarding cryptographic keys,” Proceeding of AFIPS, Vol 48, pp 313–317, 1979

Google Scholar

[3] C Blundo, A D Santis, R D Simone, and U Vaccaro, “Tight bounds on the information rate of secret sharing schemes,” Designs, Codes and Cryptography, Vol 11, No 1, pp 1–25, 1997

Google Scholar

[4] E F Brickell and D R Stinson, “Some improved bounds on the information rate of perfect secret sharing schemes,” Journal of Cryptology, Vol 5, No 3, pp 152–166, 1992

Google Scholar

[5] H Y Chien, J K Jan, and Y M Tseng, “A practical (t, n) multi-secret sharing scheme,” IEICE Transactions on Fundamentals, Vol E83-A, No 12, pp 2762–2765, 2000

Google Scholar

國際替代計量

利用超圖所設計之對於一般授權者集合的完美機密配置系統

全文下載

主題瀏覽