學術產出-學位論文

題名 安全多方計算平行演算法之實證研究
An Empirical Study on the Parallel Implementation of Secure Multi-Party Computation
作者 王啟典
Wang, Chi-Tien
貢獻者 陳恭
Chen, Kung
王啟典
Wang, Chi-Tien
關鍵詞 安全多方計算
Scalar product
平行演算法
時間公式
Secure multi-party computation
Scalar product
Parallel algorithm
Time function
日期 2008
上傳時間 8-十二月-2010 12:03:06 (UTC+8)
摘要 安全多方計算是資訊安全研究裡的一個重要主題,其概念為多方在不洩漏各自私有資訊下能一起完成某種函式的計算。在安全多方計算研究領域裡,有一種作法是以scalar product來當作計算的基礎演算邏輯單元,重而建構其他更複雜的安全多方計算。本論文首先針對scalar product發展一套平行性實作架構,藉此我們再實作出多個不同演算法之comparison計算,其中包含了循序演算法以及平行演算法。我們透過實驗來找出適當的平行計算基礎架構與影響執行時間效能的主要因子,並以執行時間效能上的分析來推導相關時間公式。由上述實證研究我們對於不同演算法之comparison計算來作執行時間效能的預測,從實驗結果可以得知我們推導出來之時間公式極為準確,希望能給予使用者在執行comparison計算有所考量,使其在不同執行環境執行comparison計算能有最佳的執行時間效能。
Loosely speaking, secure multi-party computation (SMC) involves computing functions with inputs from two or more parties in a distributed network while ensuring that no additional information, other than what can be inferred from each participant’s input and output, is revealed to parties not privy to that information. This thesis concerns the parallel implementation of SMC using a scalar-product (SP) based approach. In this approach, SP is considered as the basic building block for constructing more complex SMC. My thesis first develops a concurrent architecture for implementing two-party scalar product computation. Then it implements several algorithms of secure comparison. Finally, a series of experiments are conducted to collect performance statistics for building time functions that can predict the execution time of comparison computation based on that of the scalar product and other parameters, such as CPU core numbers. From the experimental results, we find that these time functions are very accurate. Hence we argue that these time functions can assist users to obtain the better runtime performance for comparison protocols under their specific execution environments.
參考文獻 [1] A. C. Yao, “Protocols for secure computations,” in Proceedings of the 23rd Annual IEEE Symposium on the Foundations of Computer Science, November 1982, pp. 160-164.
[2] O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game,” in STOC ’87: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM Press, 1987, pp. 218-229.
[3] P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft, Multiparty Computation Goes Live, Cryptology ePrint Archive Report 2008/068, 2008.
[4] I.-C. Wang, C.-H. Shen, T.-S. Hsu, C.-C. Liao, D.-W. Wang, and J. Zhan, “Towards empirical aspects of secure scalar product,” in ISA ’08: IEEE International Conference on Information Security and Assurance, April 2008, pp. 573-578.
[5] C.-H. Shen, J. Zhan, T.-S. Hsu, C.-J. Liau, and D.-W. Wang, “Scalar-product based secure two-party computation,” in GrC ’08: IEEE International Conference on Granular Computing, Aug. 2008, pp. 556-561.
[6] D.-W. Wang, C.-J. Liau, Y.-T. Chiang, and T.-S. Hsu, “Information theoretical analysis of two-party secret computation,” Data and Applications Security XX, Lecture Notes in Computer Science, vol. 4127, pp. 310–317, 2006.
[7] C.-H. Shen, J. Zhan, D.-W. Wang, T.-S. Hsu, and C.-J. Liau, “Information-theoretically secure number-product protocol,” in ICMLC ’07: International Conference on Machine Learning and Cybernetics, vol. 5, 19-22 Aug. 2007, pp. 3006-3011.
[8] O. Goldreich, Foundations of Cryptography, Volume II Basic Applications, 1st ed. Cambridge University Press, 2004.
[9] D. Beaver, “Commodity-based cryptography (extended abstract),” in STOC ’97: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM Press, 1997, pp.446–455.
[10] W. Du and Z. Zhan, “A practical approach to solve secure multiparty computation problems,” in NSPW ’02: Proceedings of the 2002 workshop on New security paradigms. New York, NY, USA: ACM Press, 2002, pp. 127–135.
[11] Juan G., Berry S., and José V., “Practical and Secure Solutions for Integer Comparison”, pp. 330-342, PKC2007
[12] I. Damgård, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft, “Unconditionally secure constant-rounds multiparty computation for equality, comparison, bits and exponentiation,” in TCC 2006: Proceedings of the 3rd Theory of Cryptography Conference, 2006, pp. 285-304.
[13] J. Bar-Ilan and D. Beaver, “Non-Cryptographic Fault-Tolerant Computing in Constant Number of Rounds of Interaction,” Proc. ACM PODC ’89, pp. 201-209.
描述 碩士
國立政治大學
資訊科學學系
96753026
97
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0096753026
資料類型 thesis
dc.contributor.advisor 陳恭zh_TW
dc.contributor.advisor Chen, Kungen_US
dc.contributor.author (作者) 王啟典zh_TW
dc.contributor.author (作者) Wang, Chi-Tienen_US
dc.creator (作者) 王啟典zh_TW
dc.creator (作者) Wang, Chi-Tienen_US
dc.date (日期) 2008en_US
dc.date.accessioned 8-十二月-2010 12:03:06 (UTC+8)-
dc.date.available 8-十二月-2010 12:03:06 (UTC+8)-
dc.date.issued (上傳時間) 8-十二月-2010 12:03:06 (UTC+8)-
dc.identifier (其他 識別碼) G0096753026en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/49469-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 96753026zh_TW
dc.description (描述) 97zh_TW
dc.description.abstract (摘要) 安全多方計算是資訊安全研究裡的一個重要主題,其概念為多方在不洩漏各自私有資訊下能一起完成某種函式的計算。在安全多方計算研究領域裡,有一種作法是以scalar product來當作計算的基礎演算邏輯單元,重而建構其他更複雜的安全多方計算。本論文首先針對scalar product發展一套平行性實作架構,藉此我們再實作出多個不同演算法之comparison計算,其中包含了循序演算法以及平行演算法。我們透過實驗來找出適當的平行計算基礎架構與影響執行時間效能的主要因子,並以執行時間效能上的分析來推導相關時間公式。由上述實證研究我們對於不同演算法之comparison計算來作執行時間效能的預測,從實驗結果可以得知我們推導出來之時間公式極為準確,希望能給予使用者在執行comparison計算有所考量,使其在不同執行環境執行comparison計算能有最佳的執行時間效能。zh_TW
dc.description.abstract (摘要) Loosely speaking, secure multi-party computation (SMC) involves computing functions with inputs from two or more parties in a distributed network while ensuring that no additional information, other than what can be inferred from each participant’s input and output, is revealed to parties not privy to that information. This thesis concerns the parallel implementation of SMC using a scalar-product (SP) based approach. In this approach, SP is considered as the basic building block for constructing more complex SMC. My thesis first develops a concurrent architecture for implementing two-party scalar product computation. Then it implements several algorithms of secure comparison. Finally, a series of experiments are conducted to collect performance statistics for building time functions that can predict the execution time of comparison computation based on that of the scalar product and other parameters, such as CPU core numbers. From the experimental results, we find that these time functions are very accurate. Hence we argue that these time functions can assist users to obtain the better runtime performance for comparison protocols under their specific execution environments.en_US
dc.description.tableofcontents 第一章 導論................................................1
1.1 研究動機...............................................1
1.2 研究目標...............................................3
1.3 研究貢獻...............................................4
1.4 論文章節架構...........................................5
第二章 相關研究與技術背景..................................6
2.1 Information-Theory Based Security Definition...........6
2.2 The Compositional Theorem..............................6
2.3 Building Block.........................................7
2.4 Scalar Product Protocol................................8
2.5 Product Protocol.......................................9
2.6 A Commodity-Based Approach To Scalar Product Protocol...................................................9
第三章 Scalar Product Protocol系統架構設計與實作..........11
3.1 Scalar Product Protocol系統架構設計...................11
3.1.1 Scalar Product Protocol原有系統架構設計.............11
3.1.2 Scalar Product Protocol平行系統架構設計.............12
3.2 Scalar Product Protocol平行系統架構之實作方法.........13
3.3 Experimental Result...................................15
第四章 Comparison Algorithms..............................18
4.1 Original Comparison Algorithm.........................18
4.1.1 Original Comparison Algorithm之實作方法.............21
4.1.2 Original Comparison Algorithm之實驗結果.............22
4.2 Linear Rounds Comparison Algorithm....................23
4.2.1 Linear Rounds Comparison Algorithm之實作方法........25
4.2.2 Linear Rounds Comparison Algorithm之實驗結果........27
4.3 Logarithmic Rounds Comparison Algorithm...............29
4.3.1 Logarithmic Rounds Comparison Algorithm之實作方法...31
4.3.2 Logarithmic Rounds Comparison Algorithm之實驗結果...33
4.4 Constant Rounds Comparison Algorithm..................34
4.4.1 Constant Rounds Comparison Algorithm之實作方法......36
4.4.2 Constant Rounds Comparison Algorithm之實驗結果......38
4.5 Summary of Comparison Algorithms......................38
第五章 執行效能分析.......................................43
5.1 Scalar Product Protocol...............................43
5.2 Original Comparison Protocol..........................45
5.3 Logarithmic Rounds Comparison Protocol................47
5.4 Performance Evaluation................................50
第六章 結論與未來研究.....................................51
參考文獻..................................................52
附錄......................................................54
zh_TW
dc.format.extent 94059 bytes-
dc.format.extent 118080 bytes-
dc.format.extent 121044 bytes-
dc.format.extent 201050 bytes-
dc.format.extent 265286 bytes-
dc.format.extent 270059 bytes-
dc.format.extent 317090 bytes-
dc.format.extent 549208 bytes-
dc.format.extent 346113 bytes-
dc.format.extent 230866 bytes-
dc.format.extent 88486 bytes-
dc.format.extent 97491 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0096753026en_US
dc.subject (關鍵詞) 安全多方計算zh_TW
dc.subject (關鍵詞) Scalar productzh_TW
dc.subject (關鍵詞) 平行演算法zh_TW
dc.subject (關鍵詞) 時間公式zh_TW
dc.subject (關鍵詞) Secure multi-party computationen_US
dc.subject (關鍵詞) Scalar producten_US
dc.subject (關鍵詞) Parallel algorithmen_US
dc.subject (關鍵詞) Time functionen_US
dc.title (題名) 安全多方計算平行演算法之實證研究zh_TW
dc.title (題名) An Empirical Study on the Parallel Implementation of Secure Multi-Party Computationen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] A. C. Yao, “Protocols for secure computations,” in Proceedings of the 23rd Annual IEEE Symposium on the Foundations of Computer Science, November 1982, pp. 160-164.zh_TW
dc.relation.reference (參考文獻) [2] O. Goldreich, S. Micali, and A. Wigderson, “How to play any mental game,” in STOC ’87: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM Press, 1987, pp. 218-229.zh_TW
dc.relation.reference (參考文獻) [3] P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft, Multiparty Computation Goes Live, Cryptology ePrint Archive Report 2008/068, 2008.zh_TW
dc.relation.reference (參考文獻) [4] I.-C. Wang, C.-H. Shen, T.-S. Hsu, C.-C. Liao, D.-W. Wang, and J. Zhan, “Towards empirical aspects of secure scalar product,” in ISA ’08: IEEE International Conference on Information Security and Assurance, April 2008, pp. 573-578.zh_TW
dc.relation.reference (參考文獻) [5] C.-H. Shen, J. Zhan, T.-S. Hsu, C.-J. Liau, and D.-W. Wang, “Scalar-product based secure two-party computation,” in GrC ’08: IEEE International Conference on Granular Computing, Aug. 2008, pp. 556-561.zh_TW
dc.relation.reference (參考文獻) [6] D.-W. Wang, C.-J. Liau, Y.-T. Chiang, and T.-S. Hsu, “Information theoretical analysis of two-party secret computation,” Data and Applications Security XX, Lecture Notes in Computer Science, vol. 4127, pp. 310–317, 2006.zh_TW
dc.relation.reference (參考文獻) [7] C.-H. Shen, J. Zhan, D.-W. Wang, T.-S. Hsu, and C.-J. Liau, “Information-theoretically secure number-product protocol,” in ICMLC ’07: International Conference on Machine Learning and Cybernetics, vol. 5, 19-22 Aug. 2007, pp. 3006-3011.zh_TW
dc.relation.reference (參考文獻) [8] O. Goldreich, Foundations of Cryptography, Volume II Basic Applications, 1st ed. Cambridge University Press, 2004.zh_TW
dc.relation.reference (參考文獻) [9] D. Beaver, “Commodity-based cryptography (extended abstract),” in STOC ’97: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. New York, NY, USA: ACM Press, 1997, pp.446–455.zh_TW
dc.relation.reference (參考文獻) [10] W. Du and Z. Zhan, “A practical approach to solve secure multiparty computation problems,” in NSPW ’02: Proceedings of the 2002 workshop on New security paradigms. New York, NY, USA: ACM Press, 2002, pp. 127–135.zh_TW
dc.relation.reference (參考文獻) [11] Juan G., Berry S., and José V., “Practical and Secure Solutions for Integer Comparison”, pp. 330-342, PKC2007zh_TW
dc.relation.reference (參考文獻) [12] I. Damgård, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft, “Unconditionally secure constant-rounds multiparty computation for equality, comparison, bits and exponentiation,” in TCC 2006: Proceedings of the 3rd Theory of Cryptography Conference, 2006, pp. 285-304.zh_TW
dc.relation.reference (參考文獻) [13] J. Bar-Ilan and D. Beaver, “Non-Cryptographic Fault-Tolerant Computing in Constant Number of Rounds of Interaction,” Proc. ACM PODC ’89, pp. 201-209.zh_TW