Publications-Theses
Article View/Open
Publication Export
-
題名 多維度拉丁方陣及其臨界集之構造與應用
The Construction and Applications of Latin k-hypercube and Its Critical Sets作者 陳淑美
Chen, Shu-Mei貢獻者 左瑞麟
Tso, Ray-Lin
陳淑美
Shu-Mei Chen關鍵詞 拉丁方陣
拉丁立體方陣
多維度拉丁方陣
臨界集
秘密分享方案
Latin squares
Latin cubes
Latin k-hypercubes
Critical set
Secret sharing schemes日期 2018 上傳時間 10-Aug-2018 11:11:39 (UTC+8) 摘要 「資訊安全」之相關研究如密碼學（Cryptography）、秘密分享方案(Secret sharing schemes)經常運用數學技術來設計與實踐，如1994年Cooper,Donovan和Seberry便舉出了如何運用拉丁方陣(Latin squares)來實踐秘密分享方案。 拉丁方陣為組合設計(Combinatorial designs)中的一部分，於現代密碼學及編碼的設計，有相當多的貢獻。 本論文將以組合設計中的拉丁方陣為基礎，進一步發展出拉丁立體方陣(Latin cubes)的相關方法論，包含如何建構拉丁立體方陣、如何找出拉丁立體方陣的臨界集(Critical sets)、如何由拉丁立體方陣的臨界集反推出拉丁立體方陣等，藉此增強拉丁方陣應用的複雜度及多元性，本論文亦依據拉丁立體方陣相關方法論發展出多維度拉丁方陣（稱之為Latin k-hypercubes）之相關方法論，也成功地將所提出之方法論運用至資訊隱藏領域。希望本論文所提出之方法論，後續可於資訊安全各類研究領域發展出更多相關應用。
Researches related to "information security" such as Cryptography and Secret sharing schemes are usually designed and constructed using mathematical techniques. For example,in 1994 Cooper, Donovan and Seberry showed the method how to use the Latin square to design secret sharing schemes. The design of Latin squares are in the scope of the Combinatorial designs, and they have considerable contributions to Cryptography and coding theory. This thesis will develop the Latin cubes methodology based on the concepts of Latin squares and their critical sets. We will introduce how to construct a Latin cube,how to find the critical sets of the Latin cube,and how to rebuild the Latin cube using its critical sets and so on. The idea introduced here can be used to increase the complexity and diversity of the application of the Latin squares. Based on the methodology of Latin cubes,we will also develop the multi-dimensional Latin squares (called the Latin k-hypercubes) methodology,and show how it can be successfully applied to the areas of information hiding. We hope that the methodologies proposed in this thesis can be followed by more relevant applications in various fields of information security researches.參考文獻 [1] A. P. Street.(Math. 21 ,1992).Defining sets for t-designs and critical sets for Latin squares.New Zealand J. [2] A. P. Street and D. J. Street.(1987).Combinatorics of Experimental Design.Oxford University Press, Oxford. [3] B. Smetaniuk.(Math. 16 ,1979）.On the minimal critical set of a Latin square. [4] Blakley,G. R.（1979）.Safeguarding cryptographic keys . Proceedings of the National Computer Conference 48. [5] Chin-ChenChang ,Yung-ChenChou,The Duc Kieu.（2008）.An Information Hiding Scheme Using Sudoku.The 3rd Intetnational .Conference on Innovative Computing Information and Control (ICICIC`08) 978-0-7695-3161-8/08 © 2008 IEEE [6] Cooper, J.,Donovan, D. , Seberry, J..( 4,1991) . Latin squares and critical sets of minimal size. Australas. J. Combin. [7] Donovan, D., Cooper, J., Nott, D.J., Seberry, J..( 1995 ) .Latin squares: critical sets and their lower bounds. Ars Combin. 39 [8] Donovan, D., Cooper, J..( 1996 ) .Critical sets in back circulant Latin squares. Aequationes Math. [9] D. Curran and G. H. J. van Rees.( 1978) . Critical sets in Latin squares. Congr. Numer. 22 [10] D. Raghavarao.(1988).Constructions and Combinatorial Problems in Design of Experiments. Dover Publications, New York [11] D. R. Stinson.(1996).Combinatorial Designs with Selected Applications. Lecture Notes, Dept. Comput. Sci., Univ. Manitoba, Winnipeg. [12] Daniel R. Droz.(2016).Orthogonal Sets of Latin Squares and Class-r Hypercubes Generated by Finite Algebraic Systems. Submitted in Partial Fulfillment of the Requirements for the Degree of Doctor in Eberly College of Science of the Pennsylvania State University. [13] D. R. Stinson and G. H. J. van Rees.(1982).Some large critical sets. Congr. Numer. 34. [14] Hung-Li Fu.(2002).Combinatorial Designs ( Lecture Notes ).available at http://hlfu.math.nctu.edu.tw/course.php?YEAR=91. [15] J. Cooper, D. Donovan and J. Seberry.(Appl. 12 ,1994). Secret sharing schemes arising from Latin square. Bull. Inst. Combin. [16] Jerzy Wojdyło(Southeast Missouri State University).(2007). Latin Squares, Cubes and Hypercubes. available at https://www.slideserve.com/vangie/Latin-squares-cubes-and-hypercubes. [17] Pria Bharti, Roopali Soni.(November 2012).A New Approach of Data Hiding in Images using Cryptography and Steganography.International Journal of Computer Applications (0975 – 8887) Volume 58– No.18. [18] R. Tso, Y. Miao.(2017).A survey of secret sharing schemes based on Latin squares.(Conference Paper),13th International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IIH-MSP 2017. [19] R. Mathon and A. Rosa.(1996) . 2-(v,k,λ) Designs of small order, in C. J. Colbourn and J. H. Dinitz, eds..The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton [20] Shamim Ahmed Laskar1 and Kattamanchi Hemachandran .(December 2012).High Capacity data hiding using LSB Steganography and Encryption. International Journal of Database Management Systems ( IJDMS ) Vol.4, No.6, December 2012. [21] Shamir, Adi,(1979).How to share a secret. Communications of the ACM 22 (11). [22] Shamir, A.(1979) . How to share a secret, Comm. ACM 22. [23] Smetaniuk, B.(1979) . On the minimal critical set of a Latin square. Util. Math. 16, 97–100 [24] Steven T. Dougherty , Theresa A. Szczepanski.(2008).Latin k-hypercubes .Australasian Journal of Combinatorics Volume 40. [25] Stinson, D.R., van Rees, G.H.J. .(1982) . Some large critical sets. Congr. Numer. 34, 441–456. [26] Street, A.P.(Math. 21, 1992) . Defining sets for t -designs and critical sets for Latin squares, New Zealand J. [27] Tamara Gomez, Phoebe Coy.(2015).Latin Squares: Critical Sets.available at http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Latin%20Squares%20Presentation%201.pdf. [28] Vaipuna Raass.(2016) .Critical Sets of Full Latin squares.A thesis submitted in fulfilment of the requirements for the DegreeOf Doctor of Philosophy at the University of Waikato. [29] 冷輝世,游孟霖 ,曾顯文.(2014).基於 LSB 的適性高負載資訊隱藏法. International Journal of Science and Engineering Vol.4 No.1:225-228 [30] 維基百科https://en.wikipedia.org/wiki/Hypercube [31]維基百科拉丁方陣的數量https://zh.wikipedia.org/wiki/%E6%8B%89%E4%B8%81%E6%96%B9%E9%99%A3 描述 碩士
國立政治大學
資訊科學系碩士在職專班
105971006資料來源 http://thesis.lib.nccu.edu.tw/record/#G0105971006 資料類型 thesis dc.contributor.advisor 左瑞麟 zh_TW dc.contributor.advisor Tso, Ray-Lin en_US dc.contributor.author (Authors) 陳淑美 zh_TW dc.contributor.author (Authors) Shu-Mei Chen en_US dc.creator (作者) 陳淑美 zh_TW dc.creator (作者) Chen, Shu-Mei en_US dc.date (日期) 2018 en_US dc.date.accessioned 10-Aug-2018 11:11:39 (UTC+8) - dc.date.available 10-Aug-2018 11:11:39 (UTC+8) - dc.date.issued (上傳時間) 10-Aug-2018 11:11:39 (UTC+8) - dc.identifier (Other Identifiers) G0105971006 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/119323 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系碩士在職專班 zh_TW dc.description (描述) 105971006 zh_TW dc.description.abstract (摘要) 「資訊安全」之相關研究如密碼學（Cryptography）、秘密分享方案(Secret sharing schemes)經常運用數學技術來設計與實踐，如1994年Cooper,Donovan和Seberry便舉出了如何運用拉丁方陣(Latin squares)來實踐秘密分享方案。 拉丁方陣為組合設計(Combinatorial designs)中的一部分，於現代密碼學及編碼的設計，有相當多的貢獻。 本論文將以組合設計中的拉丁方陣為基礎，進一步發展出拉丁立體方陣(Latin cubes)的相關方法論，包含如何建構拉丁立體方陣、如何找出拉丁立體方陣的臨界集(Critical sets)、如何由拉丁立體方陣的臨界集反推出拉丁立體方陣等，藉此增強拉丁方陣應用的複雜度及多元性，本論文亦依據拉丁立體方陣相關方法論發展出多維度拉丁方陣（稱之為Latin k-hypercubes）之相關方法論，也成功地將所提出之方法論運用至資訊隱藏領域。希望本論文所提出之方法論，後續可於資訊安全各類研究領域發展出更多相關應用。 zh_TW dc.description.abstract (摘要) Researches related to "information security" such as Cryptography and Secret sharing schemes are usually designed and constructed using mathematical techniques. For example,in 1994 Cooper, Donovan and Seberry showed the method how to use the Latin square to design secret sharing schemes. The design of Latin squares are in the scope of the Combinatorial designs, and they have considerable contributions to Cryptography and coding theory. This thesis will develop the Latin cubes methodology based on the concepts of Latin squares and their critical sets. We will introduce how to construct a Latin cube,how to find the critical sets of the Latin cube,and how to rebuild the Latin cube using its critical sets and so on. The idea introduced here can be used to increase the complexity and diversity of the application of the Latin squares. Based on the methodology of Latin cubes,we will also develop the multi-dimensional Latin squares (called the Latin k-hypercubes) methodology,and show how it can be successfully applied to the areas of information hiding. We hope that the methodologies proposed in this thesis can be followed by more relevant applications in various fields of information security researches. en_US dc.description.tableofcontents 第一章 緒論 1 1.1 研究動機、背景 1 1.2 研究方法及目標 3 1.3 研究貢獻 3 1.4 論文架構 4 第二章 背景知識與相關研究 5 2.1 拉丁方陣相關方法論 5 2.2 拉丁立體方陣(Latin Cubes) 10 2.3 拉丁立體方陣指數式表示法 12 2.4 多維度拉丁方陣 13 2.5 數獨(Sudoku） 16 2.6 資訊隱藏之隱密術 16 2.7 秘密分享方案(Secret Sharing) 20 第三章 拉丁立體方陣相關方法論 21 3.1 如何建構拉丁立體方陣 21 3.2 拉丁立體方陣結構分析 25 3.3 拉丁立體方陣臨界集 29 3.4 如何產生拉丁立體方陣之臨界集及還原拉丁立體方陣 31 3.5 拉丁立體方陣相關方法論之演算法 41 第四章 多維度拉丁方陣相關方法論 47 4.1 如何建構多維度拉丁方陣 47 4.2 多維度拉丁方陣結構分析 51 4.3 多維度拉丁方陣之臨界集 60 4.4 如何產生多維度拉丁方陣臨界集及還原多維度拉丁方陣 62 4.5 多維度拉丁方陣方法論程式實作與驗證 77 4.6 以拉丁立體方陣指數式表示法建構之拉丁立體方陣如何運用本論文 提出之方法論求出其臨界集及反推拉丁立體方陣 92 4.7 多維度拉丁方陣相關方法論之演算法 96 4.8 多維度拉丁方陣之安全性評估 104 第五章 多維度拉丁方陣的應用 106 5.1 應用於秘密分享方案 106 5.2 應用於資訊隱藏 106 第六章 總結 118 參考文獻 119 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0105971006 en_US dc.subject (關鍵詞) 拉丁方陣 zh_TW dc.subject (關鍵詞) 拉丁立體方陣 zh_TW dc.subject (關鍵詞) 多維度拉丁方陣 zh_TW dc.subject (關鍵詞) 臨界集 zh_TW dc.subject (關鍵詞) 秘密分享方案 zh_TW dc.subject (關鍵詞) Latin squares en_US dc.subject (關鍵詞) Latin cubes en_US dc.subject (關鍵詞) Latin k-hypercubes en_US dc.subject (關鍵詞) Critical set en_US dc.subject (關鍵詞) Secret sharing schemes en_US dc.title (題名) 多維度拉丁方陣及其臨界集之構造與應用 zh_TW dc.title (題名) The Construction and Applications of Latin k-hypercube and Its Critical Sets en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] A. P. Street.(Math. 21 ,1992).Defining sets for t-designs and critical sets for Latin squares.New Zealand J. [2] A. P. Street and D. J. Street.(1987).Combinatorics of Experimental Design.Oxford University Press, Oxford. [3] B. Smetaniuk.(Math. 16 ,1979）.On the minimal critical set of a Latin square. [4] Blakley,G. R.（1979）.Safeguarding cryptographic keys . Proceedings of the National Computer Conference 48. [5] Chin-ChenChang ,Yung-ChenChou,The Duc Kieu.（2008）.An Information Hiding Scheme Using Sudoku.The 3rd Intetnational .Conference on Innovative Computing Information and Control (ICICIC`08) 978-0-7695-3161-8/08 © 2008 IEEE [6] Cooper, J.,Donovan, D. , Seberry, J..( 4,1991) . Latin squares and critical sets of minimal size. Australas. J. Combin. [7] Donovan, D., Cooper, J., Nott, D.J., Seberry, J..( 1995 ) .Latin squares: critical sets and their lower bounds. Ars Combin. 39 [8] Donovan, D., Cooper, J..( 1996 ) .Critical sets in back circulant Latin squares. Aequationes Math. [9] D. Curran and G. H. J. van Rees.( 1978) . Critical sets in Latin squares. Congr. Numer. 22 [10] D. Raghavarao.(1988).Constructions and Combinatorial Problems in Design of Experiments. Dover Publications, New York [11] D. R. Stinson.(1996).Combinatorial Designs with Selected Applications. Lecture Notes, Dept. Comput. Sci., Univ. Manitoba, Winnipeg. [12] Daniel R. Droz.(2016).Orthogonal Sets of Latin Squares and Class-r Hypercubes Generated by Finite Algebraic Systems. Submitted in Partial Fulfillment of the Requirements for the Degree of Doctor in Eberly College of Science of the Pennsylvania State University. [13] D. R. Stinson and G. H. J. van Rees.(1982).Some large critical sets. Congr. Numer. 34. [14] Hung-Li Fu.(2002).Combinatorial Designs ( Lecture Notes ).available at http://hlfu.math.nctu.edu.tw/course.php?YEAR=91. [15] J. Cooper, D. Donovan and J. Seberry.(Appl. 12 ,1994). Secret sharing schemes arising from Latin square. Bull. Inst. Combin. [16] Jerzy Wojdyło(Southeast Missouri State University).(2007). Latin Squares, Cubes and Hypercubes. available at https://www.slideserve.com/vangie/Latin-squares-cubes-and-hypercubes. [17] Pria Bharti, Roopali Soni.(November 2012).A New Approach of Data Hiding in Images using Cryptography and Steganography.International Journal of Computer Applications (0975 – 8887) Volume 58– No.18. [18] R. Tso, Y. Miao.(2017).A survey of secret sharing schemes based on Latin squares.(Conference Paper),13th International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IIH-MSP 2017. [19] R. Mathon and A. Rosa.(1996) . 2-(v,k,λ) Designs of small order, in C. J. Colbourn and J. H. Dinitz, eds..The CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton [20] Shamim Ahmed Laskar1 and Kattamanchi Hemachandran .(December 2012).High Capacity data hiding using LSB Steganography and Encryption. International Journal of Database Management Systems ( IJDMS ) Vol.4, No.6, December 2012. [21] Shamir, Adi,(1979).How to share a secret. Communications of the ACM 22 (11). [22] Shamir, A.(1979) . How to share a secret, Comm. ACM 22. [23] Smetaniuk, B.(1979) . On the minimal critical set of a Latin square. Util. Math. 16, 97–100 [24] Steven T. Dougherty , Theresa A. Szczepanski.(2008).Latin k-hypercubes .Australasian Journal of Combinatorics Volume 40. [25] Stinson, D.R., van Rees, G.H.J. .(1982) . Some large critical sets. Congr. Numer. 34, 441–456. [26] Street, A.P.(Math. 21, 1992) . Defining sets for t -designs and critical sets for Latin squares, New Zealand J. [27] Tamara Gomez, Phoebe Coy.(2015).Latin Squares: Critical Sets.available at http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/Latin%20Squares%20Presentation%201.pdf. [28] Vaipuna Raass.(2016) .Critical Sets of Full Latin squares.A thesis submitted in fulfilment of the requirements for the DegreeOf Doctor of Philosophy at the University of Waikato. [29] 冷輝世,游孟霖 ,曾顯文.(2014).基於 LSB 的適性高負載資訊隱藏法. International Journal of Science and Engineering Vol.4 No.1:225-228 [30] 維基百科https://en.wikipedia.org/wiki/Hypercube [31]維基百科拉丁方陣的數量https://zh.wikipedia.org/wiki/%E6%8B%89%E4%B8%81%E6%96%B9%E9%99%A3 zh_TW dc.identifier.doi (DOI) 10.6814/THE.NCCU.EMCS.005.2018.B02 -
