臺灣博碩士論文加值系統

機密分享為一簡單保護機密資訊之方法，自 Blakley 與 Shamir 於 1979 年分別提出實做機制後，機密分享領域備受關注至今。舉例說明，不論是 Shamir 的多項式內插法技巧、Blakley 的有限幾何學應用或 1989 年 Schellenberg 與 Stinson 所提出之組合設計方式，都相當經典且令人玩味。本文針對基於線性碼與線性系統的機密分享，分別探究兩者於門檻存取結構及一般化存取結構下建構機密分享的可行性，所提出的機制中，我們將基於線性碼的 Massey 與 Karnin 之機制一般化，其餘基於線性系統則為創新的機制；我們不僅設計了演算法亦分析了這些機制的安全性，使得機密分享更具多樣性與實用性。

Secret sharing is an elegant approach for safeguarding information. Since the first schemes invented by Shamir and Blakley independently in 1979, the research of secret sharing has attracted much attention. Skills including polynomial interpolation by Shamir, finite geometries by Blakley and combinatorial designs by Schellenberg and Stinson (1989), to name a few, are so classical that inspire many researchers in this research area. In this thesis, we intend to explore the feasibilities of the constructions of secret sharing schemes in threshold and general access structures using linear codes and linear systems respectively. The proposed linear codes-based schemes are generalized from Mseesy’s and Karnin’s schemes; whereas those by linear systems are innovative. We not only design algorithms but also analyze the security for these schemes. It is expected that this study might enrich the diversity and practicality of secret sharing.

摘要 i
Abstract ii
謝誌 iii
圖目錄 vii
表目錄 ix
第 1 章 緒論 1
1.1. 研究背景與動機 1
1.2. 研究問題 2
1.3. 論文大綱 3
第 2 章 文獻探討 4
2.1. 機密分享 4
2.2. (r, n) 門檻存取結構 5
2.2.1. Shamir (r, n) 門檻存取結構機制 6
2.2.2. Blakley (r, n) 門檻存取結構機制 8
2.2.3. Karnin-Greene-Hellman (r, n) 門檻存取結構機制 10
2.3. 一般化存取結構 13
2.3.1. Ito-Saito-Nishizeki 一般化存取結構之多重指派機制 13
2.3.2. Tan-Zhu 一般化存取結構之多重指派機制 16
2.4. Massey基於線性碼的一般化存取結構 18
2.4.1. Massey 基於線性碼的機密分享機制的性質與定義 19
2.4.2. Massey 機密分享機制演算法 24
2.4.3. Massey 機密分享機制範例 25
第 3 章 研究成果與討論 28
3.1. 基於線性系統的 (r, n) 門檻存取結構 28
3.1.1. Shamir 與 Blakley 機密分享機制於線性系統 29
3.1.2. 設計基於線性系統的 (r, n) 門檻存取結構機密分享 34
3.2. 基於線性碼的 (r, n) 門檻存取結構 37
3.2.1. 設計基於線性碼的 (r, n) 門檻存取結構機密分享 37
3.3. 基於線性系統的一般化存取結構 40
3.3.1. 一般化存取結構機密之多重指派問題 41
3.3.2. 設計基於線性系統的一般化存取結構機密分享機制 44
3.4. 基於線性碼的一般化存取結構 51
3.4.1. Massey 一般化存取結構機密分享機制的限制 52
3.4.2. 設計基於線性碼的一般化存取結構機密分享機制 53
3.5. 基於線性系統的機密分享機制架構 56
第 4 章 實驗結果 58
4.1. 基於線性系統的 (r, n) 門檻存取結構 58
4.1.1. 實驗結果 58
4.1.2. 安全性分析 64
4.2. 基於線性碼的 (r, n) 門檻存取結構 65
4.2.1. 實驗結果 65
4.2.2. 安全性分析 70
4.3. 基於線性系統的一般化存取結構 71
4.3.1. 實驗結果 71
4.3.2. 安全性分析 87
4.4. 基於線性碼的一般化存取結構 89
4.4.1. 實驗結果 89
4.4.2. 安全性分析 93
第 5 章 結論及未來研究 96
參考文獻 98
附錄 A. 解多項式展開係數 104
附錄 B. GF(q) 與 GF(qn) 105
附錄 C. 線性碼 108
附錄 D. 錯誤更正碼、同位檢查碼及同位檢查矩陣 110

[1] A. Ashikhmin and A. Barg, “Minimal vectors in linear codes,” IEEE Trans. Inf. Theory, vol. 44, no. 5, 1998, pp. 2010–2017.
[2] A. Beimel and Y. Ishai, “On the Power of Nonlinear Secret-Sharing”, IEEE Conf. on Computational Complexity, 2001, pp. 188–202.
[3] A. Canteaut, P. Charpin, and H. Dobbertin, “Weight divisibility of cyclic codes, highly nonlinear functions on GF(2m), and cross correlation of maximum-length sequences,” SIAM J. Discr. Math., vol. 13, 2000, pp. 105–137.
[4] A. Renvall and C. Ding, “The Access Structure of Some Secret-Sharing Schemes,” in Information Security and Privacy (Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, vol. 1172, 1996, pp. 67-78.
[5] A. Renvall and C. Ding, “A nonlinear secret sharing scheme,” in ACISP: Information Security and Privacy: Australasian Conference, vol. 1172 of Lecture Notes in Computer Science, 1996, pp. 56–66.
[6] A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, 1979, pp. 612–613.
[7] C. Carlet and C. Ding, “Highly nonlinear mappings,” J. Complexity, vol. 20, no. 2, 2004, pp. 205–244.
[8] C. Carlet and C. Ding, “Linear Codes From Perfect Nonlinear Mappings and Their Secret Sharing Schemes”, IEEE Trans. Inf. Theory, vol. 51, no. 6, 2005, pp. 2089–2102.
[9] C. Charnes, J. Pieprzyk and R. Safavi-Naini, “Conditionally secure secret sharing scheme with disenrollment capability,” in 2nd ACM Conference on Computer and Communications Security, ACM Press, 194, pp. 89-95.
[10] C. Charnes and J. Pieprzyk, “Cumulative arrays and generalized Shamir secret sharing schemes,” in Seventeenth Annual Computer Science Conference (ACSC17), New Zealand (G. Gupta, ed.), Australian Computer Science Communications, vol. 16 of ISBN 0-473-02313-X, ch. Part C, 1994, pp. 519-528.
[11] C. Ding and J. Yuan, “Covering and Secret Sharing with Linear Codes,” in Discrete Mathematics and Theoretical Computer Science (Lecture Notes in Computer Science). Berlin, Germany: Springer-Verlag, vol. 2731, 2003, pp. 11–25.
[12] C. L. Liu. Introduction to Combinatorial mathematics. McGraw-Hill, 1968.
[13] C. S. Laih, L. Harn, and C. C. Chang, “Contemporary. Cryptography and Its Applications,” UNALIS CORPORATION, 2001.
[14] D. Chen and D. R. Stinson, “Recent results on combinatorial constructions for threshold schemes.” Australas. J. Combin., vol. 1, 1990, pp. 29-48.
[15] D. R. Stinson, “An explication of secret sharing schemes,” Des., Codes Cryptography., vol. 2, no. 4, 1992, pp. 357–390.
[16] D. R. Stinton and S. A. Vanstone, “A combinatorial approach to threshold scheme,” Advance in Cryptology-Proceedings Crypto ’87 (C. Pomerrance, ed.), Lecture Notes in Computer Science, vol. 293, Springer-Verlag, Berlin, 1988, pp. 330-339.
[17] E. Brickell and D. Stinson, “Some Improved Bounds on the Information Rate of Perfect Secret Sharing Schemes,” in Advances in Cryptology-Proceedings of CRYPTO ’90 (A. Menezes and S. Vanstone, eds.), vol. 537 of Lecture Notes in Computer Science, 1991, pp 242-252, Springer-Verlag. also, Journal of Cryptology, vol. 5, no. 3, 1992, pp. 153-166.
[18] E. D. Karnin, J. W. Greene, and M. E. Hellman. “On secret sharing systems,” IEEE Trans. Inf. Theory, vol. 29, no. 1, 1983, pp. 35–41.
[19] E. F. Brickell, “Ideal secret sharing schemes,” In Advances in Cryptology- Eurocrypt89 (Lecture Notes in Computer Science), vol. 434, 1990, pp. 468–475. Springer.
[20] E. F. Brickell and D. M. Davenport, “On the classification of ideal secret sharing schemes,” Journal of Cryptology, vol. 4, no. 2, 1991, pp. 123-134, Springer.
[21] F. J. MacWilliams and N. J. A. Sloane, “The Theory of Error Correcting Codes,” Amsterdam, The Netherlands: North-Holland, 1978.
[22] G. R. ,Blakley, “Safeguarding cryptographic keys,” in AFIPS Conf. Proc., vol. 48, 1979, pp. 313-317.
[23] G. R. Blakley and G. A. Kabatianskii, “Linear algebra approach to secret sharing schemes,” in Error Control, Cryptology, and Speech Compression, Selected Papers from Int. Workshop Information Protection (Lecture Notes in Computer Science, vol. 829). Berlin, Germany: Springer-Verlag, 1994, pp. 33–40.
[24] G. Simmons, “Robust shared secret schemes or How to be sure you have the right answer even through you don’t know the question”, Congr. no. 68, 1989, pp. 215-248.
[25] G. Simmons, “How to (Really) Share a Secret,” Advances in Cryptology–Proceedings of CRYPTO ’88, vol. 403 of Lecture Notes in Computer Science, 1990, pp. 390-448, Springer-Verlag.
[26] G. Simmons, “Prepositioned Shared Secret and/or Shared Control Schemes,” in Advances in Cryptology-Proceedings of EUROCRYPT ’89 (J.-J. Quisquater and J. Vandewalle, eds.), vol. 434 of Lecture Notes in Computer Science, 1990, pp. 436-467, Springer-Verlag.
[27] G. Simmons, W. A. Jackson, and K. Martin, “The geometry of shared secret schemes,” Bull. ICA, vol. 1, 1991, pp. 71-88.
[28] G. V. Bard, “Algebraic Cryptanalysis,” Springer, 2009, ISBN: 978-0387887562.
[29] H. Chen and R. Kramer, “Algebraic geometric secret sharing schemes and secure multi-party computations over small fields,” In CRYPTO 2006, 2006, pp. 521-536. Springer-Verlag.
[30] Hakan O¨zadam, Ferruh O¨ zbudak and Zu¨lfu¨kar Saygı, “Secret Sharing Schemes and Linear Codes,” Information Security and Cryptology Conference with International Participation, 2007.
[31] H. Yamamoto, “On secret sharing systems using (k, L, n) threshold schemes,” Trans. IECE Japan J68-A, 1985, pp. 945-952.
[32] J. Benaloh and J. Leichter, “Generalized Secret Sharing and Monotone Functions,” in Advances in Cryptology-Proceedings of CRYPTO ’88 (S. Goldwasser, ed.), vol. 403 of Lecture Notes in Computer Science, 1990, pp 27-35, Springer-Verlag.
[33] J. L. Massey, “Minimal codewords and secret sharing,” in Proc. 6th Joint Swedish–Russian Workshop on Information Theory, 1993, pp. 246–249.
[34] J. L. Massey, “Some applications of coding theory,” Cryptography, codes and Ciphers: Cryptography and Coding IV, 1995, pp. 33–47.
[35] J. L. Massey, “Three Coding Problems,” Report in Trondhjemsgade 3, 2TH DK-2100 Copenhagen, Denmark 2009.
[36] J. Pieprzyk, and X. M. Zhang, “Ideal Threshold Schemes from MDS Codes,” Discrete Mathematics and Theoretical Computer Science, vol. 6, no. 2, 2004, pp. 471–482.
[37] J. Yuan and C. Ding, “Secret sharing schemes from two-weight codes,” The Bose Centenary Symposium on Discrete Mathematics and Applications, Kolkata, Dec 2002.
[38] J. Yuan and C. Ding, “Secret sharing schemes from three classes of linear codes,” IEEE Trans. Inf. Theory, vol. 52, no. 1, 2006, pp. 206–212.
[39] K. J. Tan and H. W. Zhu, “General secret sharing scheme,” Computer Communications, vol.22, 1999, pp. 755– 757.
[40] K. M. Martin, “New secret sharing schemes from old,” Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 14, 1993, pp. 65-77.
[41] K. Okada and K. Kurosawa, “MDS secret sharing scheme secure against cheaters,” IEEE Trans. Inf. Theory, vol. 46, no. 3, 2000, pp. 1078-1081.
[42] M. Ito, A. Saito and T. Nishizeki, “Secret sharing scheme realizing general access structure,” in Proceedings IEEE Global Telecommun. Conf., Glbecom ’87 Washington, 1987, pp.99–102, IEEE Communications Soc. Press.
[43] Marten van Dijk, “A Linear Construction of Perfect Secret Sharing Schemes,” Proc. of Eurocrypt’94, Lecture Notes in Computer Science, Springer-Verlag, Berlin, vol. 950, 1995, pp. 23–34.
[44] Marten van Dijk, “On the information rate of perfect secret sharing schemes,” Designs, Codes, and Cryptography, Vol. 6, 1995, pp. 143–169.
[45] Marten van Dijk, W. A. Jackson, and K. M. Martin, “A duality theorem for incomplete secret sharing schemes,” Bulletin of the Institute of Combinatorics and its Application, Vol. 19, 1997, pp. 93–101.
[46] Marten van Dijk, W. A. Jackson, and K. M. Martin, “A general decomposition construction for incomplete secret sharing schemes,” submitted to Designs, Codes and Cryptography, 1995.
[47] P. J. Schellenberg and D. R. Stinson, “Threshold schemes from combinatorial designs,” Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 5, no. 4, 1989, pp. 143-160
[48] R. Anderson, C. Ding, T. Helleseth, and T. Klove, “How to build robust shared control systems,” Designs, Codes and Cryptography, vol. 15, 1998, pp. 111–124.
[49] R. J. McEliece and D. V. Sarwate, “On sharing secrets and Reed-Solomon codes,” Comm. ACM, Vol. 24, 1981, pp. 583-584.
[50] R. Lidl and H. Niederreiter, “Finite Fields,” Cambridge, U.K.: Cambridge Univ. Press, 1997.
[51] T. Tassa and J. L. Villar, “On proper secrets, (t, k)-bases and linear codes,” Designs, Codes and Cryptography, vol. 52, no. 2, 2009, pp. 129-154, Springer.
[52] T. Shifrin and M. Adams, “Linear Algebra: A Geometric Approach,” W. H. Freeman and Company 2009, ISBN: 978-1429215213.
[53] T. Xiaoqing and W. Zhiguo. “New secret sharing scheme based on linear code.,” Applied Mathematics - A Journal of Chinese Universities, vol. 19, no. 2, 2004, pp. 160–166.
[54] W. A. Jackson and K. Martin, “Cumulative Arrays and Geometric Secret Sharing Schemes,” in Advances in Cryptology-Proceedings of AUSCRYPT ’92 (J. Seberry and Y. Zheng, eds.), vol. 718 of Lecture Notes in Computer Science, 1993, pp. 48-55, Springer-Verlag.
[55] W. A. Jackson and K. Martin, “Geometric secret sharing schemes and their duals,” Designs, Codes and Cryptography, vol. 4, 1994, pp. 83–95.
[56] W. A. Jackson and K. M. Martin, “Perfect secret sharing schemes on five participants,” to appear in Designs, Codes and Cryptography.
[57] Y. Zheng, T. Hardjono and J. Seberry, “Reusing shares in secret sharing schemes,” The Computer Journal, vol. 37, 1994, pp. 199-205.
[58] 趙啟超。數學傳播，十八卷四期。民 83 年 12 月。