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

題名 模組化之安全多方計算領域專屬腳本語言
A Modular Scripting Language for Secure Multi-Party Computation
作者 翁宸暉
Weng, Cheng Hui
貢獻者 陳恭
Chen, Kung
翁宸暉
Weng, Cheng Hui
關鍵詞 安全多方計算
隱私保護
領域專屬語言
靜態分析
Secure multi-party computation
Privacy protection
Domain-specific language
Static analysis
日期 2012
上傳時間 2-Sep-2013 16:49:23 (UTC+8)
摘要 安全多方計算的研究主要是針對在分散環境下的兩造(或多方)之間，如何在不透露彼此私有的資料的情況下，計算一個約定函數的問題，並要確保除了計算結果及其可能推導出的資訊，不會洩漏額外的私有資料。依此要求設計出來的函數算法，稱為安全的多方計算協定。
本研究室曾根據一套基於向量內積運算發展出的多方安全計算方法，設計了一個分散式系統框架與符合安全需求的函式庫。其後再以自動化使用這套函式庫的動機出發，開發出多方安全計算語言 smcSL (secure multiparty computation Scripting Language)。然此套語言目前尚缺作為使用者表述與解決問題重要工具的自定函式功能，以及模組化相關功能。本研究即於現有 smcSL 的基礎，在安全性受到保證的情況下，允許使用者於程式中自定函式與模組，使編寫更複雜且實際的應用成為可能，並在設計上希望能達到下列四點目標
一、 保持原有smcSL之安全特性:包括對於各變數存取權限的檢查，以及相應產生程式碼在防止資訊洩漏上的安全考量。
二、 函式導向的語言設計原則：引入函式的同時，也代表引入所謂的變數作用區域，以及相應的特性。因此像變數遮蔽（Variable Shadowing）、全域變數、區域變數、傳值或傳參等議題，皆是設計上的要點。
三、 相容現有成果：在smcSL語言正在持續發展的階段，維持執行環境的相容是必要的。最理想的情況是不修改而只是增加原有執行環境的功能，就可以使新特色運作順暢。
四、 擴充與靈活性：在smcSL持續發展的情況下，有必要為了可預見的需求留下設計擴充的餘地。因此在實作與設計上，帶有新特色的smcSL語言編譯器，以及其他組件，都會遵循此原則進行。
Recently, language-based tools are emerging to better support the systematic development of secure multiparty computation (SMC) protocols. In particular, our colleagues had developed a scripting language for automating the development of complex protocols for a commodity-based approach to SMC.
The implementation of the language consists of two parts, namely a distributed runtime environment and library of SMC protocols in the Ruby language and a compiler to translate a SMC script to executable Ruby code exploiting the distributed SMC runtime environment.
The basic constructs of our scripting languages are pretty common, such as variables, data types, expressions, assignment statements and for-loops. The salient features of our language are a symmetric view of all participating parties and a three-level data security attributes, namely public, private, and shared, that users can employ to express their security requirements by associating variables with these attributes in a declarative manner. Furthermore, these security attributes also direct how our compiler should perform security check as well as code generation.
However, currently the scripting language lacks of modular constructs such as functions and modules found in most programming languages, thus making it difficult for developers to compose large programs without redundant code. To make our language more flexible and practical, this thesis presents an enhancement of smcSL with functions and a basic module facility, and discusses how and why their design and implementation can still follows the security requirements, which ensures our new features not only make developers apt to construct large programs, but also keep them secure.
參考文獻 [1] Andrew C. Yao . Protocols for secure computation. SFCS 1982: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science; 1982 Nov 3-5; 1982. p. 160-4.

[2] Oded Goldreich, Silvio M Micali, Avi WigdersonA. How to play ANY mental game.Proceedings of the 19th Annual ACM Symposium on Theory of Computing; 1987. p. 218-29.

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

[4] Oded Goldreich. Secure multi-party computation (working draft). Available from http://www.wisdom.weizmann.ac.il/~oded/foc-vol2.html, 1998.

[5] Moni Naor, Benny Pinkas, and Reuban Sumner. Privacy preserving auctions and mechanism design. In ACM Conf. on Electronic Commerce, pages 129–139, 1999.

[6] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Secure evaluation of private linear branching programs with medical applications. In European Symposium on Research in Computer Security (ESORICS’09), volume 5789 of LNCS, pages 424–439.Springer, 2009.

[7] Ahmad-Reza Sadeghi , Thomas Schneider, and Immo Wehrenberg. Efficient privacy-preserving face recognition.In 12th International Conference on Information Security and Cryptology (ICISC ’09), LNCS.Springer, 2009.

[8] Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval.In Proceedings of IEEE Symp.on Foundations of Computer Science, Milwaukee, WI USA, October 23-25 1995.

[9] Yehuda Lindell and Benny Pinkas . Secure multiparty computation for privacy-preserving data mining. J. of Privacy and Confidentiality, 1(1):59–98, 2009.


[10] Wenliang Du and Mikhail J. Atallah . Secure multi-party computation problems and their applications: A review and open problems. In New Security Paradigms Workshop, pages 11-20, Cloudcroft, New Mexico, USA, September 11-13 2001.

[11] 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.

[12] Ivan Damgård and Mats Jurik. A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. In Public-Key Cryptography (PKC’01), volume 1992 of LNCS, pages 119–136.Springer, 2001.

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

[14] 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.

[15] 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.

[16] 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, pages 310-317, July 2006.

[17] 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.




[18] 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.


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

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

[21] 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.

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

[23] Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, 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.

[24] Wilko Henecka, Stefan K ögl, Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In ACM Conference on Computer and Communications Security (ACM CCS’10), pages 451–462. ACM, 2010.

[25] Andrew C. Yao, “Protocols for secure computations (extended abstract),”in FOCS, 1982, pp. 160–164.

[26] Wenliang Du and Zhijun Zhan, “A practical approach to solve secure multi-party computation problems,” in Proceedings of the 2002 workshop on New security paradigms, ser. NSPW ’02. New York, NY, USA: ACM, 2002, pp. 127–135.

[27] Yi-Ting Chiang, Da-Wei Wang, Churn-Jung Liau, and Tsan-sheng Hsu. “Secrecy of two-party secure computation,” in DBSec, 2005, pp. 114–123.

[28] Da-Wei Wang, Churn-Jung Liau, Yi-Ting Chiang, and Tsan-sheng Hsu. Information theoretical analysis of two-party secret computation,” in DBSec, 2006, pp. 310–317.
描述 碩士
國立政治大學
資訊科學學系
100753039
101
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0100753039
資料類型 thesis
dc.contributor.advisor 陳恭zh_TW
dc.contributor.advisor Chen, Kungen_US
dc.contributor.author (Authors) 翁宸暉zh_TW
dc.contributor.author (Authors) Weng, Cheng Huien_US
dc.creator (作者) 翁宸暉zh_TW
dc.creator (作者) Weng, Cheng Huien_US
dc.date (日期) 2012en_US
dc.date.accessioned 2-Sep-2013 16:49:23 (UTC+8)-
dc.date.available 2-Sep-2013 16:49:23 (UTC+8)-
dc.date.issued (上傳時間) 2-Sep-2013 16:49:23 (UTC+8)-
dc.identifier (Other Identifiers) G0100753039en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/59444-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 100753039zh_TW
dc.description (描述) 101zh_TW
dc.description.abstract (摘要) 安全多方計算的研究主要是針對在分散環境下的兩造(或多方)之間，如何在不透露彼此私有的資料的情況下，計算一個約定函數的問題，並要確保除了計算結果及其可能推導出的資訊，不會洩漏額外的私有資料。依此要求設計出來的函數算法，稱為安全的多方計算協定。
本研究室曾根據一套基於向量內積運算發展出的多方安全計算方法，設計了一個分散式系統框架與符合安全需求的函式庫。其後再以自動化使用這套函式庫的動機出發，開發出多方安全計算語言 smcSL (secure multiparty computation Scripting Language)。然此套語言目前尚缺作為使用者表述與解決問題重要工具的自定函式功能，以及模組化相關功能。本研究即於現有 smcSL 的基礎，在安全性受到保證的情況下，允許使用者於程式中自定函式與模組，使編寫更複雜且實際的應用成為可能，並在設計上希望能達到下列四點目標
一、 保持原有smcSL之安全特性:包括對於各變數存取權限的檢查，以及相應產生程式碼在防止資訊洩漏上的安全考量。
二、 函式導向的語言設計原則：引入函式的同時，也代表引入所謂的變數作用區域，以及相應的特性。因此像變數遮蔽（Variable Shadowing）、全域變數、區域變數、傳值或傳參等議題，皆是設計上的要點。
三、 相容現有成果：在smcSL語言正在持續發展的階段，維持執行環境的相容是必要的。最理想的情況是不修改而只是增加原有執行環境的功能，就可以使新特色運作順暢。
四、 擴充與靈活性：在smcSL持續發展的情況下，有必要為了可預見的需求留下設計擴充的餘地。因此在實作與設計上，帶有新特色的smcSL語言編譯器，以及其他組件，都會遵循此原則進行。		zh_TW
dc.description.abstract (摘要) Recently, language-based tools are emerging to better support the systematic development of secure multiparty computation (SMC) protocols. In particular, our colleagues had developed a scripting language for automating the development of complex protocols for a commodity-based approach to SMC.
The implementation of the language consists of two parts, namely a distributed runtime environment and library of SMC protocols in the Ruby language and a compiler to translate a SMC script to executable Ruby code exploiting the distributed SMC runtime environment.
The basic constructs of our scripting languages are pretty common, such as variables, data types, expressions, assignment statements and for-loops. The salient features of our language are a symmetric view of all participating parties and a three-level data security attributes, namely public, private, and shared, that users can employ to express their security requirements by associating variables with these attributes in a declarative manner. Furthermore, these security attributes also direct how our compiler should perform security check as well as code generation.
However, currently the scripting language lacks of modular constructs such as functions and modules found in most programming languages, thus making it difficult for developers to compose large programs without redundant code. To make our language more flexible and practical, this thesis presents an enhancement of smcSL with functions and a basic module facility, and discusses how and why their design and implementation can still follows the security requirements, which ensures our new features not only make developers apt to construct large programs, but also keep them secure.		en_US
dc.description.tableofcontents 緒論 1
1-1研究背景與動機 1
1-2研究目標 4
1-3研究貢獻 4
1-4論文結構 4
既有研究成果介紹 5
2-1自動化多方安全協定函式庫的使用 5
2-2本機與分散式運算 5
2-3存取權限對 SMCSL 變數的重要性 6
2-4 SMCSL 程式編譯與執行的環境與流程 7
2-4-1 基礎環境 8
2-4-2撰寫與編譯 smcSL 程式 8
2-4-3執行中：各機器間的互動 9
2-4-4 計算完的處理 9
2-5 相關研究的概況與評述 10
研究方法與標的 11
3-1原SMCSL 文法因應新增函式功能之變更 11
3-2 函式文法介紹 15
3-3 函式檢查規則 19
3-3-1 函式作用區域檢查 19
3-3-2 缺少回傳陳述式 20
3-3-3 回傳值與宣告不一致 20
函式生成規則 21
4-1 SMCSL函式生成原則與實例 21
4-2存取權限轉換於函式方面的議題 27
SMCSL編譯器設計原則與實作 29
5-1 SMCSL編譯器語法層面處理流程 29
5-2抽象語法樹的檢查階段 34
5-2-1 變數與函式作用區域檢查 34
5-2-2 型別檢查 36
5-2-3 存取權限檢查 37
5-3 SMCSL編譯器安全檢查設計原則與實作 38
5-4 SMCSL編譯器目的碼產生設計原則與實作 39
研究成果討論 42
6-1 向後相容並適度更新 42
6-2 低耦合設計之必要性與成本討論 44
6-3 模組化SMCSL程式之開發方式 46
結論 50
7-1 本研究貢獻 50
7-2 未來研究 50
參考文獻 54		zh_TW
dc.format.extent 2829852 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0100753039en_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 (關鍵詞) Static analysisen_US
dc.title (題名) 模組化之安全多方計算領域專屬腳本語言zh_TW
dc.title (題名) A Modular 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 the 23rd Annual IEEE Symposium on Foundations of Computer Science; 1982 Nov 3-5; 1982. p. 160-4.

[2] Oded Goldreich, Silvio M Micali, Avi WigdersonA. How to play ANY mental game.Proceedings of the 19th Annual ACM Symposium on Theory of Computing; 1987. p. 218-29.

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

[4] Oded Goldreich. Secure multi-party computation (working draft). Available from http://www.wisdom.weizmann.ac.il/~oded/foc-vol2.html, 1998.

[5] Moni Naor, Benny Pinkas, and Reuban Sumner. Privacy preserving auctions and mechanism design. In ACM Conf. on Electronic Commerce, pages 129–139, 1999.

[6] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad-Reza Sadeghi, and Thomas Schneider. Secure evaluation of private linear branching programs with medical applications. In European Symposium on Research in Computer Security (ESORICS’09), volume 5789 of LNCS, pages 424–439.Springer, 2009.

[7] Ahmad-Reza Sadeghi , Thomas Schneider, and Immo Wehrenberg. Efficient privacy-preserving face recognition.In 12th International Conference on Information Security and Cryptology (ICISC ’09), LNCS.Springer, 2009.

[8] Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. Private information retrieval.In Proceedings of IEEE Symp.on Foundations of Computer Science, Milwaukee, WI USA, October 23-25 1995.

[9] Yehuda Lindell and Benny Pinkas . Secure multiparty computation for privacy-preserving data mining. J. of Privacy and Confidentiality, 1(1):59–98, 2009.


[10] Wenliang Du and Mikhail J. Atallah . Secure multi-party computation problems and their applications: A review and open problems. In New Security Paradigms Workshop, pages 11-20, Cloudcroft, New Mexico, USA, September 11-13 2001.

[11] 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.

[12] Ivan Damgård and Mats Jurik. A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. In Public-Key Cryptography (PKC’01), volume 1992 of LNCS, pages 119–136.Springer, 2001.

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

[14] 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.

[15] 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.

[16] 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, pages 310-317, July 2006.

[17] 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.




[18] 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.


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

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

[21] 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.

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

[23] Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, 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.

[24] Wilko Henecka, Stefan K ögl, Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: Tool for Automating Secure Two-partY computations. In ACM Conference on Computer and Communications Security (ACM CCS’10), pages 451–462. ACM, 2010.

[25] Andrew C. Yao, “Protocols for secure computations (extended abstract),”in FOCS, 1982, pp. 160–164.

[26] Wenliang Du and Zhijun Zhan, “A practical approach to solve secure multi-party computation problems,” in Proceedings of the 2002 workshop on New security paradigms, ser. NSPW ’02. New York, NY, USA: ACM, 2002, pp. 127–135.

[27] Yi-Ting Chiang, Da-Wei Wang, Churn-Jung Liau, and Tsan-sheng Hsu. “Secrecy of two-party secure computation,” in DBSec, 2005, pp. 114–123.

[28] Da-Wei Wang, Churn-Jung Liau, Yi-Ting Chiang, and Tsan-sheng Hsu. Information theoretical analysis of two-party secret computation,” in DBSec, 2006, pp. 310–317.		zh_TW