1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 安全多方計算腳本語言smcSL之效能改進
Performance enhancements for smcSL, a scripting language for secure multi-party computation
作者 李家宇
Li, Jia Yu
貢獻者 陳恭
Chen, Kung
李家宇
Li, Jia Yu
關鍵詞 安全多方計算
隱私保護
領域專屬語言
編譯器優化
Secure multi-party computation
Privacy protection
Domain-specific language
Optimizing compiler
日期 2014
上傳時間 2-Mar-2015 10:13:24 (UTC+8)
摘要 安全多方計算（Secure multi-party computation, SMC）的研究主要是針對分散環境下的兩方或多方在計算一個約定函數問題時，能夠在不透漏彼此私有資料的情況下，不失安全性的計算出結果。smcSL 爲一個安全多方計算腳本語言，是為了能夠自動化使用符合安全需求的函式庫（SMC-Protocol）而發展出來的。目前此腳本語言runtime以Ruby執行，且產生盡量多的smc運算來確保安全性。我們的研究將針對以上兩個限制去改寫編譯器，讓它能夠產生C++目的碼並在不失安全性的前提下改寫expression運算，進而減少smc運算的數量以達到效率的提升。由於數學中二元運算存在Rule1:交換律和結合律、Rule2:分配律等性質， 使得expression的改寫能不影響運算結果。編譯器會透過重排順序、提出因數等方式改寫expression，讓不必要的 smc二元運算子降為local運算，使得smcSL的效能獲得改進。
Secure multiparty 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.
Recently, language-based tools are emerging to better support the systematic development of SMC protocols. In particular, smcSL is a scripting language developed by our laboratory for automating the development of complex protocols for an information-theoretical approach to secure multiparty computation. This scripting language models the participating parties in a peer-to-peer symmetric manner that each party holds their private data as well as any intermediate results jointly. The smcSL language enables users to express their requirements of "the right to use a piece of data" in a simple yet abstract way and its compiler can detect any potential breaches of those security requirements specified in a user script.
However, for safety purpose, the compiler generates object code by using a lot of SMC protocols. This conservative strategy leads to inefficient runtime performance. This thesis investigates how to apply compiler optimization techniques such as algebraic simplification to improve the runtime performance of generated code. Specifically, we enhance the compiler with an optimization module that uses associative, commutative and distributive law to rewrite computation expressions so that unnecessary invocations of SMC protocols will be replaced by execution of local computations. As a result, the computation and communication cost of generated code will be reduced explicitly.
參考文獻 [1] Andrew C. Yao . Protocols for secure computation. SFCS 1982: Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science; 1982 Nov 3-5; 1982. P. 160-4

[2] Andrew C. Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations of Computer Science(FOCS’ 86), pages 162-167.IEEE, 1986.

[3] Pascal Paillier, Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology – EUROCRYPT’ 99, volume 1592 of LNCS, pages 223 – 238. Springer, 1999.

[4] Ivan Damgard and Mats Jurik. A generalization, a simplification and some applications of paillier’s probabilistic public-key system. In Public-Key Cryptography(PKC’ 01), volume 1992 of LNCS, page 119-136.Springer, 2001.

[5] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Advances in Cryptology – EUROCRYPT’ 10, LNCS, page 24-43. Springer, 2010.

[6] Donald Beaver. Commodity-based cryptography(extended abstract), STOC 1997: Proceedings of the 29th Annual ACM Symposium on Theory of Computing; 1997 May 4-6; El Paso, Texas, USA. New York, NY, USA: ACM Press; 1997. p.446-55.

[7] Wenliang Du, Zhijun Zhan. A practical approach to solve Secure Multi-party Computation problems, NSPW 2002: Proceedings of the 2002 Workshop on New Security Paradigms; 2002 Sep 23-26; Virginia Beach, Virginia USA. New York, NY, USA:ACM Press; 2002. p. 127-35

[8] Da-Wei Wang, Chrun-Jung Liau, Yi-Ting Chiang, Tsan-sheng Hsu, “Information Theoretical Analysis of Two-Party Secret Computation,”Data and Application Security, Lecture Notes in Computer Science, number 4127, Springer, page 310-317, July 2006.

[9] Chih-HaoShen, Justin Zhan, Da-Wei Wang, Tsan-Sheng Hsu, Churn-Jung Liau, “Information-Theoretically Secure Number-Product Protocol,” 2007 International Conference on Machine Learning and Cybernetics, volume 5, pages 3006-3011, August 2007.

[10] I-Cheng Wang, Chih-Hao Shen, Justin Zhan, Tsan-sheng Hsu, Churn-Jung Liau, and Da-Wei Wang, “Towards Empirical Aspects of Secure Scalar Product,” IEEE Transactions on Systems, Man, and Cybernetics, volume 39, pages 440-447, July 2009.

[11] 蕭名宏，基於多方安全計算之算術運算，國立政治大學資訊科學系，碩士論文，民99年7月。

[12] 黃文楷，安全多方計算協定描述語言之設計與實作，國立政治大學資訊科學系，碩士論文，民100年7月。

[13] 翁宸暉，模組化之安全多方計算領域專屬腳本語言，國立政治大學資訊科學系，碩士論文，民102年7月。

[14] Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. Fairplay – a secure two-party computation system. In Proceedings of USENIX Security Symposium, pages 287 -302, Aug. 2004.

[15] Janus Dam Nielsen and Micheal I. Schwartzbach. A domain-specific programming language for secure multiparty computation. In Workshop on Programming Languages and Analysis for Security(PLAS’ 07), page 21-30. ACM, 2007.

[16] Peter Bogetoft, Dan Lund Christensen, Ivan Damg˚ard, Martin Geisler,
Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielsen, Jakob Pagter, Michael Schwartzbach, Tomas Toft. Secure Multparty Computation Goes Live. In 13th International Conference on Financial Cryptography and Data Security; 2009 Feb 23-26; Barbados. 2009. p. 325-43.

[17] Wilko Henecka, Stefan Kögl, Ahmad-Reza Sadeghi, Thomas Schneider, Immo Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In ACM Conference on Computer and Communication Security(ACM CCS’ 10), page 451-462. ACM, 2010.
[18] I.C. Wang, Kung Chen, J.H. Lee, T.S. Hsu, C.J. Liau, P.Y. Wang, and D.W. Wang, ”On Applying Secure Multiparty Computation: A Case Report”, Proc. Of Asia-Pacific Association Medical Informatics(APAMI 2009), Hiroshima, Japan, Nov. 22-24, 2009.

[19] 疾病管制局，登革色疾病負擔之估計與應用，行政院衛生署疾病管制局97年度科技研究發展計畫。

[20] Chih-Hao Shen, Justin Zhany, Da-Wei Wang, Tsan-sheng Hsu, Churn-Jung Liau. Information-theoretically Secure Number-product Protocol. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, 19-22 August 2007.

[21] Florian Kerschbaum, “Expression Rewriting for Optimizing Secure Computation”, In Conference on Data and Application Security and Privacy, 2013.
描述 碩士
國立政治大學
資訊科學學系
101753033
103
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0101753033
資料類型 thesis
dc.contributor.advisor 陳恭zh_TW
dc.contributor.advisor Chen, Kungen_US
dc.contributor.author (Authors) 李家宇zh_TW
dc.contributor.author (Authors) Li, Jia Yuen_US
dc.creator (作者) 李家宇zh_TW
dc.creator (作者) Li, Jia Yuen_US
dc.date (日期) 2014en_US
dc.date.accessioned 2-Mar-2015 10:13:24 (UTC+8)-
dc.date.available 2-Mar-2015 10:13:24 (UTC+8)-
dc.date.issued (上傳時間) 2-Mar-2015 10:13:24 (UTC+8)-
dc.identifier (Other Identifiers) G0101753033en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/73572-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 101753033zh_TW
dc.description (描述) 103zh_TW
dc.description.abstract (摘要) 安全多方計算（Secure multi-party computation, SMC）的研究主要是針對分散環境下的兩方或多方在計算一個約定函數問題時，能夠在不透漏彼此私有資料的情況下，不失安全性的計算出結果。smcSL 爲一個安全多方計算腳本語言，是為了能夠自動化使用符合安全需求的函式庫（SMC-Protocol）而發展出來的。目前此腳本語言runtime以Ruby執行，且產生盡量多的smc運算來確保安全性。我們的研究將針對以上兩個限制去改寫編譯器，讓它能夠產生C++目的碼並在不失安全性的前提下改寫expression運算，進而減少smc運算的數量以達到效率的提升。由於數學中二元運算存在Rule1:交換律和結合律、Rule2:分配律等性質， 使得expression的改寫能不影響運算結果。編譯器會透過重排順序、提出因數等方式改寫expression，讓不必要的 smc二元運算子降為local運算，使得smcSL的效能獲得改進。zh_TW
dc.description.abstract (摘要) Secure multiparty 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.
Recently, language-based tools are emerging to better support the systematic development of SMC protocols. In particular, smcSL is a scripting language developed by our laboratory for automating the development of complex protocols for an information-theoretical approach to secure multiparty computation. This scripting language models the participating parties in a peer-to-peer symmetric manner that each party holds their private data as well as any intermediate results jointly. The smcSL language enables users to express their requirements of "the right to use a piece of data" in a simple yet abstract way and its compiler can detect any potential breaches of those security requirements specified in a user script.
However, for safety purpose, the compiler generates object code by using a lot of SMC protocols. This conservative strategy leads to inefficient runtime performance. This thesis investigates how to apply compiler optimization techniques such as algebraic simplification to improve the runtime performance of generated code. Specifically, we enhance the compiler with an optimization module that uses associative, commutative and distributive law to rewrite computation expressions so that unnecessary invocations of SMC protocols will be replaced by execution of local computations. As a result, the computation and communication cost of generated code will be reduced explicitly.		en_US
dc.description.tableofcontents 圖目錄…………………………………………………………………………………………………………………3
第一章、 緒論…………………………………………………………………………………………………….5
1-1 簡介………………………………………………………………………………………………………………..5
1-2 背景知識………………………………………………………………………………………………………..5
1-3 研究動機與目的…………………………………………………………………………………………….8
1-4 研究貢獻………………………………………………………………………………………………………..9
第二章、 相關研究的概況與評述………………………………………………………………………10
2-1安全多方運算的存取權限………………….……………………………………………………..…10
2-2安全多方運算領域專屬腳本語言現況……………………………………………………..…12
2-3函式庫與編譯器改寫……………………………………………………………………………………15
2-4安全多方運算－expression運算現況…………………………………………………16
2-5 EXPRESSION REWRITING相關研究的概況與評述……………………………18
第三章、 研究方法及系統架構………………………………………………………………………….20
3-1 系統設計概念－產生新目的碼……………………………………………………………………20
3-2 系統設計概念－優化抽象語法樹……………………………………………………………..21
3-3 系統設計與元件介紹…………………………………………………………………………………..23
第四章、編譯器優化實作…………………………………………………………………………………26
　4-1編譯器GENERATOR組件切換與優化組件導入…………………………………………26
　4-2優化組件導入的預期成果…………………………………………………………………………27
　4-3 EXPRSSION優化 - COST CALCULATING…………………………………………29
　4-4 Expression Normalization……………………………………………………………30
　4-5 Rule1: Associative and Commutative……………………………………33
4-6 Rule1: Associative and Commutative流程………………………………34
　4-7 Rule2: Distributive Law…………………………………………………………………36
　4-8 Rule2: Distributive Law流程………………………………………………………36
　4-9 分析A:提出term中的smc乘法讓它被共用…………………………………………39
　4-10 分析B:將term往同類聚集使加法local化…………….………………………40
第五章、結論與未來展望………………………………………………………………………………….43
　5-1 編譯器產生C++目的碼對SMCSL效能的影響………………………………………43
　5-2 編譯器改寫Expression對smcSL效能的影響……………………………………44
　5-3 smcSL針對效能改進的未來展望…………………………………………………………………45
第六章、 參考文獻…………………………………………………………………………………………….48
附錄……………………………………………………………………………………………………………….……51		zh_TW
dc.format.extent 2593061 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0101753033en_US
dc.subject (關鍵詞) 安全多方計算zh_TW
dc.subject (關鍵詞) 隱私保護zh_TW
dc.subject (關鍵詞) 領域專屬語言zh_TW
dc.subject (關鍵詞) 編譯器優化zh_TW
dc.subject (關鍵詞) Secure multi-party computationen_US
dc.subject (關鍵詞) Privacy protectionen_US
dc.subject (關鍵詞) Domain-specific languageen_US
dc.subject (關鍵詞) Optimizing compileren_US
dc.title (題名) 安全多方計算腳本語言smcSL之效能改進zh_TW
dc.title (題名) Performance enhancements for smcSL, a scripting language for secure multi-party computationen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] Andrew C. Yao . Protocols for secure computation. SFCS 1982: Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science; 1982 Nov 3-5; 1982. P. 160-4

[2] Andrew C. Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations of Computer Science(FOCS’ 86), pages 162-167.IEEE, 1986.

[3] Pascal Paillier, Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology – EUROCRYPT’ 99, volume 1592 of LNCS, pages 223 – 238. Springer, 1999.

[4] Ivan Damgard and Mats Jurik. A generalization, a simplification and some applications of paillier’s probabilistic public-key system. In Public-Key Cryptography(PKC’ 01), volume 1992 of LNCS, page 119-136.Springer, 2001.

[5] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Advances in Cryptology – EUROCRYPT’ 10, LNCS, page 24-43. Springer, 2010.

[6] Donald Beaver. Commodity-based cryptography(extended abstract), STOC 1997: Proceedings of the 29th Annual ACM Symposium on Theory of Computing; 1997 May 4-6; El Paso, Texas, USA. New York, NY, USA: ACM Press; 1997. p.446-55.

[7] Wenliang Du, Zhijun Zhan. A practical approach to solve Secure Multi-party Computation problems, NSPW 2002: Proceedings of the 2002 Workshop on New Security Paradigms; 2002 Sep 23-26; Virginia Beach, Virginia USA. New York, NY, USA:ACM Press; 2002. p. 127-35

[8] Da-Wei Wang, Chrun-Jung Liau, Yi-Ting Chiang, Tsan-sheng Hsu, “Information Theoretical Analysis of Two-Party Secret Computation,”Data and Application Security, Lecture Notes in Computer Science, number 4127, Springer, page 310-317, July 2006.

[9] Chih-HaoShen, Justin Zhan, Da-Wei Wang, Tsan-Sheng Hsu, Churn-Jung Liau, “Information-Theoretically Secure Number-Product Protocol,” 2007 International Conference on Machine Learning and Cybernetics, volume 5, pages 3006-3011, August 2007.

[10] I-Cheng Wang, Chih-Hao Shen, Justin Zhan, Tsan-sheng Hsu, Churn-Jung Liau, and Da-Wei Wang, “Towards Empirical Aspects of Secure Scalar Product,” IEEE Transactions on Systems, Man, and Cybernetics, volume 39, pages 440-447, July 2009.

[11] 蕭名宏，基於多方安全計算之算術運算，國立政治大學資訊科學系，碩士論文，民99年7月。

[12] 黃文楷，安全多方計算協定描述語言之設計與實作，國立政治大學資訊科學系，碩士論文，民100年7月。

[13] 翁宸暉，模組化之安全多方計算領域專屬腳本語言，國立政治大學資訊科學系，碩士論文，民102年7月。

[14] Dahlia Malkhi, Noam Nisan, Benny Pinkas, and Yaron Sella. Fairplay – a secure two-party computation system. In Proceedings of USENIX Security Symposium, pages 287 -302, Aug. 2004.

[15] Janus Dam Nielsen and Micheal I. Schwartzbach. A domain-specific programming language for secure multiparty computation. In Workshop on Programming Languages and Analysis for Security(PLAS’ 07), page 21-30. ACM, 2007.

[16] Peter Bogetoft, Dan Lund Christensen, Ivan Damg˚ard, Martin Geisler,
Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielsen, Jakob Pagter, Michael Schwartzbach, Tomas Toft. Secure Multparty Computation Goes Live. In 13th International Conference on Financial Cryptography and Data Security; 2009 Feb 23-26; Barbados. 2009. p. 325-43.

[17] Wilko Henecka, Stefan Kögl, Ahmad-Reza Sadeghi, Thomas Schneider, Immo Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In ACM Conference on Computer and Communication Security(ACM CCS’ 10), page 451-462. ACM, 2010.
[18] I.C. Wang, Kung Chen, J.H. Lee, T.S. Hsu, C.J. Liau, P.Y. Wang, and D.W. Wang, ”On Applying Secure Multiparty Computation: A Case Report”, Proc. Of Asia-Pacific Association Medical Informatics(APAMI 2009), Hiroshima, Japan, Nov. 22-24, 2009.

[19] 疾病管制局，登革色疾病負擔之估計與應用，行政院衛生署疾病管制局97年度科技研究發展計畫。

[20] Chih-Hao Shen, Justin Zhany, Da-Wei Wang, Tsan-sheng Hsu, Churn-Jung Liau. Information-theoretically Secure Number-product Protocol. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, 19-22 August 2007.

[21] Florian Kerschbaum, “Expression Rewriting for Optimizing Secure Computation”, In Conference on Data and Application Security and Privacy, 2013.		zh_TW