(3.237.20.246) 您好!臺灣時間:2021/04/17 15:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王怡君
研究生(外文):Yi-Chun
論文名稱:利用超圖所設計之對於一般授權者集合的完美機密配置系統
論文名稱(外文):Using Hypergraph to Design Perfect Secret Sharing Schemes for General Access Structures
指導教授:阮夙姿
指導教授(外文):Justie Su-Tzu Juan
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:45
中文關鍵詞:機密配置系統超圖授權者集合驗證及偵測多次使用
外文關鍵詞:secret sharing schemehypergraphaccess structureverification and detectionmulti-use
相關次數:
  • 被引用被引用:0
  • 點閱點閱:122
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
機密配置系統 (secret sharing scheme) 是一種使一群參與者可以共同分享一個機密(secret)的系統。透過此機制,參與者可依據不同的權限分配到有關此機密的一些片段(share)。所謂的完美機密配置系統則表示:在此系統中,合法的參與者子集合可以透過拿出各自分到的片段來重建回這個機密;不合法的參與者集合則無法得到任何有關機密的資訊。我們稱所有合法的參與者子集合之集合為授權者集合 (access structure)。

在超圖 (hypergraph) 中,如果所有邊都是由r個點所組成,即邊的大小均為 r,我們將此圖形稱為 r 一致超圖 (r-uniform hypergraph),而基於 r 一致超圖的授權者集合,則表示可以使用一個r一致超圖來表示的授權者集合。意即,給定一超圖,當 r 個點形成一個邊時,即表此 r 個參與者可以重建回機密。
同理,(r1, r2)一致超圖則表示圖形上的邊大小均為 r1或 r2,
以此種圖形表示的授權者集合則稱為基於(r1, r2)一致超圖((r1, r2)-uniform hypergraph-based)的授權者集合。依此類推,(r1, r¬2, r3)一致超圖則表示圖形上的邊,大小均為 r1、r2或 r3,以此種圖形表示的授權者集合則稱為基於(r1, r2, r3)一致超圖((r1, r2, r3)-uniform hypergraph-based)的授權者集合。依照這樣的想法延伸,當邊的大小不再限制種類多寡時,所對應之授權者集合即成為可任意選取的一般授權者集合(general access structure)。

在此篇論文中,我們分別對基於r一致超圖、(r1, r2)一致超圖、(r1, r2, r3)一致超圖以及一般化超圖之授權者集合分別提出相對的完美機密配置系統。並且,對基於一般授權者集合的完美機密配置系統做改進:一、加入驗證片段及偵測欺騙者的功能。二、多次使用功能(使其系統所分配之片段可重複使用)。三、可驗證片段及偵測欺騙者的可多次使用之機密配置系統。
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.
中文摘要 I
Abstract III
致謝 IV
Contents VI
List of Figures VIII
List of Tables IX
1 Introduction 1
2 Related Work 6
2.1 Shamir’s (t, n)-threshold scheme 6
2.2 TUM scheme 7
2.3 Feldman’s scheme 8
2.4 Yang et al’s scheme 8
3 Three Perfect Secret Sharing Schemes for Uniform Hypergraph-
Based Access Structures 11
3.1 r-HA Scheme 11
3.1.1 Algorithm and an Example for r-HA Scheme 11
3.1.2 Security Analysis and the Information Rate for r-HA Scheme 14
3.2 (r1, r2)-HA Scheme 17
3.2.1 Algorithm and an Example for (r1,r2)-HA Scheme 18
3.2.2 Security Analysis and the Information Rate for (r1, r2)-HA
Scheme 21
3.3 (r1, r2, r3)-HA Scheme 23
3.3.1 Algorithms and an Example for (r1, r2, r3)-HA Scheme 23
3.3.2 Security Analysis and the Information Rate for (r1, r2, r3)-
HA Scheme 26
4 Four Perfect Secret Sharing Schemes for General Hypergraph-
Based Access Structure 30
4.1 G-HA Scheme 30
4.1.1 Algorithm for G-HA Scheme 30
4.1.2 Security Analysis and the Information Rate for G-HA scheme 32
4.2 G-VDHA scheme 35
4.3 G-MHA scheme 36
4.4 G-VDMHA scheme 37
5 Conclusions and Future Works 39
References 43
[1] J Benaloh and J Leichter, “Generalized secret sharing and monotone functions,” Proceeding of CRYPTO’88, pp 27–35, 1998
[2] G R Blakley, “Safeguarding cryptographic keys,” Proceeding of AFIPS, Vol 48, pp 313–317, 1979
[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
[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
[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
[6] D E R Denning, Cryptology, Data security Addison-Wesley, Reading, MA, 1983
[7] Y Desmedt, “Society and group oriented cryptography: a new concept,” Advances in Cryptography: Proceedings of Crypto’87, pp 120–127, 1987
[8] P Feldman, “A practical scheme for non-interactive verifiable secret sharing,” Proceedings of 28th Foundations of Computer Science, pp 427–437, 1987
[9] R W Hamming, Coding and information Theory Englewood Cliffs, Reading, NJ: Prentice-Hall, 1986
[10] L Harn, “Efficient sharing (broadcasting) of multiple secret,” Proceeding of IEE Computers and Digital Techniques, Vol 142, pp 237–240, 1995
[11] M Ito, A Saito, and T Nishizeki, “Multiple assignment scheme for sharing secret,” Journal of Cryptology, Vol 6, pp 15–20, 1993
[12] W A Jackson, K M Martin, and C M O’Keefe, “On sharing many secrets,” Proceeding of Asiacrypt’94, pp 42–54, 1994
[13] K Koyama, “Cryptographic key sharing methods for multi-groups and security analysis,” IECE Transition, Vol E66, No 1, pp 13–20, 1983
[14] A Shamir, “How to share a secret,” Communications of the ACM, Vol 22, No 11, pp 612–613, 1979
[15] C E Shannon, “Communication theory of secrecy systems,” Computer Security Journal, Vol 4, No 2, pp 7–66, 1990
[16] S P Shieh and H M Sun, “On constructing secret sharing schemes,” Proceeding of the IEEE INFOCOM’94, pp 1288–1292, 1994
[17] D R Stinson, “Decomposition constructions for secret sharing schemes,” IEEE Transactions on Information Theory, Vol 40, No 1, pp 118–125, 1994
[18] D R Stinson, “New construction of perfect secret sharing schemes for graphbased prohibited structures,” Computers and Electrical Engineering, Vol 25, No 4, pp 267–278, 1999
[19] H M Sun and S P Shieh, “Secret sharing in graph-based prohibited structures,” Proceeding of IEEE INFOCOM’97, pp 718–724, 1997
[20] H M Sun and S P Shieh, “Secret sharing schemes for graph-based prohibited structures,” Computers and Mathematics with Applications, Vol 36, No 7, pp 131–140, 1998
[21] K Tochikubo, “Efficient secret sharing schemes realizing general access structures,” IECE Transitions on Fundamentals, Vol E87-A, No 7, pp 1788–1797, 2004
[22] K Tochikubo, T Uyematsu, and R Matsumoto, “Efficient secret sharing schemes based on authorized subsets,” IECE Transitions on Fundamentals, Vol E88-A, No 1, pp 322–326, 2005
[23] J-J Tsai, T Hwang, and C-H Wang, “New generalized group-oriented cryptosystem based on diffie-hellman scheme,” Computer Communications, Vol 22, pp 727–729, 1999
[24] S-J Wang, “Direct construction of a secret in generalized group-oriented cryptography,” Computer Standards and Interfaces, Vol 26, pp 455–460, 2004
[25] Y F Weng and J S T Juan, “Perfect secret sharing scheme for prohibited structures based on r-uniform hypergraph,” Proceeding of the 15th Information Security Conference, pp 245–252, 2005
[26] Y F Weng and J S T Juan, “A skilled secret sharing scheme for r-uniform hypergraph-based prohibited structure,” Proceeding of the 23rd Workshop on Combinatorial Mathematics and Computation Theory, pp 336–344, 2006
[27] C-C Yang, T-Y Chang, and M-S Hwang, “A (t, n) multi-secret sharing scheme,” Applied Mathematics and Computation, pp 483–490, 2004
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔