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 Protocol Description Language for Secure Multi-Party Computation
作者 黃文楷
Huang, Wen Kai
貢獻者 陳恭
Chen, Kung
黃文楷
Huang, Wen Kai
關鍵詞 安全多方計算
隱私保護
領域專屬語言
靜態分析
Secure multi-party computation
privacy protection
domain-specific language
static analysis
日期 2010
上傳時間 4-Sep-2013 17:10:59 (UTC+8)
摘要 安全多方計算的研究主要是針對在分散環境下的兩造(或多方)之間，如何在不透露彼此私有的資料的情況下，計算一個約定函數的問題，並要確保除了計算結果及其可能推導出的資訊，不會洩漏額外的私有資料。依此設計出來的函數算法，稱為安全的多方計算協定(protocol)。
過去兩年本實驗室根據一套基於向量內積運算(scalar product)發展出的安全多方計算方法，設計了一個雛型的分散式系統框架，開發了一套符合其安全要求的常用算數運算函數庫。
但目前個別的應用問題在此系統上發展安全協定的程式時，使用者必須相當熟悉其架構與程式庫細節，才能開發所需程式，造成推廣上的障礙。有鑑於此，本論文採用領域專屬語言(domain-specific language)的方法與技術，針對一般安全多方協定程式的特徵來進行歸納與分析，找出協助其表達計算步驟的適當抽象機制，並在設計上訂定了以下目標：
1. 設計一高階語言用以描述多方安全計算，以提供使用者撰寫安全多方計算程式。
2. 檢查並確保使用者撰寫的程式不會有資訊洩漏。
3. 多方安全運算執行上能保持一定的效率。
4. 建立多方安全計算的運算流程，讓PDL與現有的運作環境配合，達到各伺服器合作運行多方安全計算的目的。

朝向這四個目標發展出一套協定描述語言與其編譯器。以便與SMC-Protocol以及其環境合作，協助領域專家以更簡便的方式來設計與實驗更多的安全多方協定。我們稱此語言為多方安全計算協定描述語言(Protocol Description Language, PDL)。
Protocols for secure multi-party computation (SMC) allow participants to share a computation while each party learns only what can be inferred from their own inputs and the output of the computation.
In the past two years, we developed an SMC implementation framework for both integers and floating numbers which comprises a set of arithmetic operations that manipulate secret values among involved parties using the scalar product protocol as the basis. Such a library of arithmetic operations is call building blocks.
But using this library is not easy. To solve individual SMC problem, programmer should knowing the given framework and protocol detail very well. This difficulty makes them won`t consider this framework while facing the need of SMC.
To ease the writing of more complex user-defined protocols, using the technique of domain-specific language, this thesis analysis the general needs of SMC, develop a domain-specific language of SMC, and implement a compiler that coverts this language to SMC code, which is executable code composed of the protocols of given framework. We called this language Protocol Description Language, PDL.
參考文獻 [1] Yao AC. 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] Goldreich O, Micali S, Wigderson A. How to play ANY mental game. Proceedings of 
 the 19th Annual ACM Symposium on Theory of Computing; 1987. p. 218-29.
[3] A. C. Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations 
 of Computer Science (FOCS’86), pages 162–167. IEEE, 1986.
[4] Goldreich O, Secure multi-party computation (working draft). Available from 
 http://www.wisdom.weizmann, ac.il/home/oded/public_html/foc.html, 1998.
[5] M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design.
 In ACM Conf. on Electronic Commerce, pages 129–139, 1999.
[6] M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A.-R. Sadeghi, and T. 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] A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face 
 recognition. In 12th International Conference on Information Security and Cryptology 
 (ICISC ’09), LNCS. Springer, 2009.
[8] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In
Proceedings of IEEE Symp. on Foundations of Computer Science, Milwaukee, WI 
 USA, October 23-25 1995.
[9] Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data 
 mining. J. of Privacy and Confidentiality, 1(1):59–98, 2009.
[10] Du and M. 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] P. 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] I. Damg°ard and M. 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, pages 119–136. Springer, 2001.
[13] M. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption 
 over the integers. In Advances in Cryptology –EUROCRYPT’10, LNCS, pages 24–43. 
 Springer, 2010.
[14] Beaver D. 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] Du W, Zhan Z. 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-Hao Shen, 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, Tsan-sheng Hsu, Churn-Jung Liau, Da-Wei Wang, and 
 Justin Zhan, "Towards Empirical Aspects of Secure Scalar Product," IEEE Transactions 
 on Systems, Man, and Cybernetics, volume 39, pages 440-447, July 2009.
[19] Wang IC, Shen CH, Chen K, Hsu TS, Liau CJ, Wang DW. An empirical study on 
 privacy and secure multi-party computation using exponentiation. Secure- Com 2009: 
 International Symposium on Secure Compu- ting; 2009 Aug 29-31; Vancouver, Canada. 
 2009. p. 182- 8.
[20] Wang IC, Chen K, Hsu TS, Liau CJ, Shen CH, Wang DW. Protocols for secure multi-
 party computation: design, implementation and performance evaluation. Institute of 
 Information Science, Academia Sinica, Taiwan; 2009 Report No.: TR-IIS-09-005.
[21] 王啟典，多方安全計算平行演算法之實證研究，國立政治大學資訊科學系，碩士
 論文，民98年7月。
[22] 蕭名宏，基於多方安全計算之算術運算，國立政治大學資訊科學系，碩士論文，
 民99年7月。
[23] I.C. Wang, Kung Chen, J.H. Chuang, C.H. Lee, T.S. Hsu, C.J. Liau, P.Y. Wang, and 
 D.W. Wang, “On Applying Secure Multi-party Computation: A Case Report”, Proc. of 
 Asia-Pacific Association Medical Informatics (APAMI 2009), Hiroshima, Japan, Nov. 
 22-24, 2009.
[24] 疾病管制局，登革熱疾病負擔之估計與應用，行政院衛生署疾病管制局97年度科
 技研究發展計畫。
[25] D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - a secure two-party computation 
 system. In Proceedings of USENIX Security Symposium, pages 287–302, Aug. 2004.
[26] J. D. Nielsen and M. 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.
[27] Bogetoft P, Christensen DL, Damgård I, Geisler M, Jakobsen T, Krøigaard M, Nielsen 
 JD, Nielsen JB, Niel- sen K, Pagter J, Schwartzbach MI, Toft T. Secure Multparty 
 Computation Goes Live. In 13th International Conference on Financial Cryptography 
 and Data Security; 2009 Feb 23-26; Barbados. 2009. p. 325-43.
[28] W. Henecka, S. Ko ̈gl, A.-R. Sadeghi, T. Schneider, and I. 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.
描述 碩士
國立政治大學
資訊科學學系
98753016
99
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0987530161
資料類型 thesis
dc.contributor.advisor 陳恭zh_TW
dc.contributor.advisor Chen, Kungen_US
dc.contributor.author (Authors) 黃文楷zh_TW
dc.contributor.author (Authors) Huang, Wen Kaien_US
dc.creator (作者) 黃文楷zh_TW
dc.creator (作者) Huang, Wen Kaien_US
dc.date (日期) 2010en_US
dc.date.accessioned 4-Sep-2013 17:10:59 (UTC+8)-
dc.date.available 4-Sep-2013 17:10:59 (UTC+8)-
dc.date.issued (上傳時間) 4-Sep-2013 17:10:59 (UTC+8)-
dc.identifier (Other Identifiers) G0987530161en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/60265-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 98753016zh_TW
dc.description (描述) 99zh_TW
dc.description.abstract (摘要) 安全多方計算的研究主要是針對在分散環境下的兩造(或多方)之間，如何在不透露彼此私有的資料的情況下，計算一個約定函數的問題，並要確保除了計算結果及其可能推導出的資訊，不會洩漏額外的私有資料。依此設計出來的函數算法，稱為安全的多方計算協定(protocol)。
過去兩年本實驗室根據一套基於向量內積運算(scalar product)發展出的安全多方計算方法，設計了一個雛型的分散式系統框架，開發了一套符合其安全要求的常用算數運算函數庫。
但目前個別的應用問題在此系統上發展安全協定的程式時，使用者必須相當熟悉其架構與程式庫細節，才能開發所需程式，造成推廣上的障礙。有鑑於此，本論文採用領域專屬語言(domain-specific language)的方法與技術，針對一般安全多方協定程式的特徵來進行歸納與分析，找出協助其表達計算步驟的適當抽象機制，並在設計上訂定了以下目標：
1. 設計一高階語言用以描述多方安全計算，以提供使用者撰寫安全多方計算程式。
2. 檢查並確保使用者撰寫的程式不會有資訊洩漏。
3. 多方安全運算執行上能保持一定的效率。
4. 建立多方安全計算的運算流程，讓PDL與現有的運作環境配合，達到各伺服器合作運行多方安全計算的目的。

朝向這四個目標發展出一套協定描述語言與其編譯器。以便與SMC-Protocol以及其環境合作，協助領域專家以更簡便的方式來設計與實驗更多的安全多方協定。我們稱此語言為多方安全計算協定描述語言(Protocol Description Language, PDL)。		zh_TW
dc.description.abstract (摘要) Protocols for secure multi-party computation (SMC) allow participants to share a computation while each party learns only what can be inferred from their own inputs and the output of the computation.
In the past two years, we developed an SMC implementation framework for both integers and floating numbers which comprises a set of arithmetic operations that manipulate secret values among involved parties using the scalar product protocol as the basis. Such a library of arithmetic operations is call building blocks.
But using this library is not easy. To solve individual SMC problem, programmer should knowing the given framework and protocol detail very well. This difficulty makes them won`t consider this framework while facing the need of SMC.
To ease the writing of more complex user-defined protocols, using the technique of domain-specific language, this thesis analysis the general needs of SMC, develop a domain-specific language of SMC, and implement a compiler that coverts this language to SMC code, which is executable code composed of the protocols of given framework. We called this language Protocol Description Language, PDL.		en_US
dc.description.tableofcontents 圖目錄 3
第一章 緒論 6
1.1 研究背景、動機 6
1.2 研究目標 6
1.3 研究貢獻 7
1.4 論文結構 7
第二章 相關研究與技術背景 8
2.1 安全多方計算研究背景 8
2.2 安全多方計算協定介紹 8
2.3 安全雙方計算函式庫 9
2.4 用以安全多方計算之領域特定語言 10
第三章 協定描述語言(PDL)與其運作環境之概要介紹 11
3.1 PDL語言介紹 11
3.2 PDL執行環境與流程： 15
3.3 PDL範例 20
第四章 PDL之設計與實作 31
4.1 Secure Multiparty Computation Protocol 介紹 31
4.2 以PDL Data Description 建構之型態環境 32
4.3 Computation Description 設計 33
4.4 Compiler Construction 34
4.5 Properties of Code Generation of PDL 37
4.6 Code Generation Examples of the PDL Compiler 39
第五章 PDL成果與性質討論 42
5.1 PDL語言討論：表達性與簡潔性 42
5.2 PDL Compiler對安全性分析的協助 45
5.3 抽象時間複雜度 47
第六章 結論 49
6.1 本研究貢獻 49
6.2 未來研究 49
參考文獻 52
附錄 55
附錄一，PDL文法 55
附錄二，Type-System Construction Rules 58
附錄三，Access Level Checking 60
附錄四，Data Type Checking 63
附錄五，PDL Generation Rules 65
附錄六，SMC-Protocol Counting Rule 75		zh_TW
dc.format.extent 579291 bytes-
dc.format.extent 3447370 bytes-
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/#G0987530161en_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 Protocol Description Language for Secure Multi-Party Computationen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] Yao AC. 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] Goldreich O, Micali S, Wigderson A. How to play ANY mental game. Proceedings of 
 the 19th Annual ACM Symposium on Theory of Computing; 1987. p. 218-29.
[3] A. C. Yao. How to generate and exchange secrets. In IEEE Symposium on Foundations 
 of Computer Science (FOCS’86), pages 162–167. IEEE, 1986.
[4] Goldreich O, Secure multi-party computation (working draft). Available from 
 http://www.wisdom.weizmann, ac.il/home/oded/public_html/foc.html, 1998.
[5] M. Naor, B. Pinkas, and R. Sumner. Privacy preserving auctions and mechanism design.
 In ACM Conf. on Electronic Commerce, pages 129–139, 1999.
[6] M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A.-R. Sadeghi, and T. 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] A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Efficient privacy-preserving face 
 recognition. In 12th International Conference on Information Security and Cryptology 
 (ICISC ’09), LNCS. Springer, 2009.
[8] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In
Proceedings of IEEE Symp. on Foundations of Computer Science, Milwaukee, WI 
 USA, October 23-25 1995.
[9] Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data 
 mining. J. of Privacy and Confidentiality, 1(1):59–98, 2009.
[10] Du and M. 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] P. 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] I. Damg°ard and M. 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, pages 119–136. Springer, 2001.
[13] M. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption 
 over the integers. In Advances in Cryptology –EUROCRYPT’10, LNCS, pages 24–43. 
 Springer, 2010.
[14] Beaver D. 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] Du W, Zhan Z. 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-Hao Shen, 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, Tsan-sheng Hsu, Churn-Jung Liau, Da-Wei Wang, and 
 Justin Zhan, "Towards Empirical Aspects of Secure Scalar Product," IEEE Transactions 
 on Systems, Man, and Cybernetics, volume 39, pages 440-447, July 2009.
[19] Wang IC, Shen CH, Chen K, Hsu TS, Liau CJ, Wang DW. An empirical study on 
 privacy and secure multi-party computation using exponentiation. Secure- Com 2009: 
 International Symposium on Secure Compu- ting; 2009 Aug 29-31; Vancouver, Canada. 
 2009. p. 182- 8.
[20] Wang IC, Chen K, Hsu TS, Liau CJ, Shen CH, Wang DW. Protocols for secure multi-
 party computation: design, implementation and performance evaluation. Institute of 
 Information Science, Academia Sinica, Taiwan; 2009 Report No.: TR-IIS-09-005.
[21] 王啟典，多方安全計算平行演算法之實證研究，國立政治大學資訊科學系，碩士
 論文，民98年7月。
[22] 蕭名宏，基於多方安全計算之算術運算，國立政治大學資訊科學系，碩士論文，
 民99年7月。
[23] I.C. Wang, Kung Chen, J.H. Chuang, C.H. Lee, T.S. Hsu, C.J. Liau, P.Y. Wang, and 
 D.W. Wang, “On Applying Secure Multi-party Computation: A Case Report”, Proc. of 
 Asia-Pacific Association Medical Informatics (APAMI 2009), Hiroshima, Japan, Nov. 
 22-24, 2009.
[24] 疾病管制局，登革熱疾病負擔之估計與應用，行政院衛生署疾病管制局97年度科
 技研究發展計畫。
[25] D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - a secure two-party computation 
 system. In Proceedings of USENIX Security Symposium, pages 287–302, Aug. 2004.
[26] J. D. Nielsen and M. 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.
[27] Bogetoft P, Christensen DL, Damgård I, Geisler M, Jakobsen T, Krøigaard M, Nielsen 
 JD, Nielsen JB, Niel- sen K, Pagter J, Schwartzbach MI, Toft T. Secure Multparty 
 Computation Goes Live. In 13th International Conference on Financial Cryptography 
 and Data Security; 2009 Feb 23-26; Barbados. 2009. p. 325-43.
[28] W. Henecka, S. Ko ̈gl, A.-R. Sadeghi, T. Schneider, and I. 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.		zh_TW