單調存取結構與門檻式秘密分享之研究

Monotone Access Structures and Threshold Secret Sharing Schemes

葉歡松(Wah-Song Yeap)

指導教授 ： 吳信龍 ； 張仁俊

國立臺北大學/電機資訊學院/通訊工程研究所/碩士(2010年)

摘要

在這篇論文，我們探討了關於門檻式秘密分享機制與單調存取結構的關係。在CRYPTO
1988中，Benaloh 和 Leichter考慮了傳統的門檻式秘密分享機制，我們稱之為一階門
檻式秘密分享機制。此外，他們還探討了單調存取結構，這是對秘密分享機制最普遍的
概念。它需要滿足的條件如下：在一群組A中，全體使用者使用其所有部分秘密訊息就
可以把原來的秘密還原。現在B是一更大的使用者群組，而其中也包括A群組，那麼原
本的秘密還是可以被B群組中之所有使用者的部分秘密還原。滿足上述條件，我們稱之
為單調存取結構。他們證明了存在一些單調存取結構是無法被一階門檻式秘密分享機制
實現。
我們則探討了二階門檻式秘密分享機制，它是透過雙階層來對秘密進行分解。在第一
階層，秘密是根據使用者的群組量來進行分解；在第二階層，每一組使用者再對他們所
擁有的部分秘密對應群組內之使用者的數量再次進行分解，然後再把分解的結果發散給
每一個在群組中的使用者。
在這篇論文裡，我們證明了存在一些單調存取結構無法被二階門檻式秘密分享機制實
現。此外，我們還探討了一類能被二階門檻式秘密分享機制實現的單調存取結構。我們
證明了這個類中的單調存取結構是可以被一階門檻式秘密分享機制所實現。

關鍵字

門檻式秘密分享機制 ； 資訊安全 ； 單調存取結構 ； 二階門檻式秘密分享機制

並列摘要

In this thesis, we study the relationship between threshold secret sharing schemes and monotone access structures. Previously, Benaloh and Leichter in [CRYPTO 1988] considered the general or traditional threshold secret sharing schemes which are called one-level threshold secret sharing schemes. Moreover, they also considered the monotone access structures which are the most general notion of secret sharing schemes. It only requires the following condition: Given a set A of user’s sub-secrets which can decrypt the original secret, if B is a set containing A, then one can also decrypt the original secret from sub-secrets in B. Benoloh and Leichter proved that there exists some monotone access structures cannot be realized by one-level threshold secret sharing schemes.
We consider the two-level threshold secret sharing schemes which divide the secret through two levels. In the first level, the secret is divided into group secrets based on the number of groups. In the second level, each group secret is divided into the user’s shared secret based on the number of users inside the group.
In this thesis, we proved that there are the monotone access structures which cannot be realized by two-level threshold secret sharing schemes. We also consider an interesting sub-class of monotone access structures realized by two-level threshold secret sharing schemes. We show that this class is within the scope of one-level threshold secret sharing schemes.

並列關鍵字

Threshold secret sharing scheme ； information security ； monotone access structures ； two-level threshold secret sharing scheme

參考文獻

[1]. J. Benaloh and J. Leichter.“Generalized Secret Sharing and Monotone Functions”.Proc. of Crypto 88, Springrt Berlag LNCS series, 25-35.

[2]. M. Ito, A. Saito, and T. Nishizeki.“Secret Sharing Scheme Realizing General Access Structure”. In Proc. Glob. Com,(1987).

[5]. S. Iftene and M. Grindei. “Weighted threshold RSA based on the Chinese Remainder Theorem”. In Proceedings of the 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007, pages 175- 181. IEEE Computer Society Press, 2007.

[8]. L. Harn. “Group-oriented (t; n) threshold digitial signature scheme and digital multisignature”. IEE Proc.-Comput. Digit. Tech., Vol. 141(5):page 307-313, 1994.

[9]. T. ElGamal. “A public key cryptosystem and signature scheme based on discrete logarithms”. IEEE Trans. Inform. Theory, Vol. 31: page 469-472, 1985.