學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 安全多方計算協定描述語言之設計與實作
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-九月-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, Kung en_US dc.contributor.author (作者) 黃文楷 zh_TW dc.contributor.author (作者) Huang, Wen Kai en_US dc.creator (作者) 黃文楷 zh_TW dc.creator (作者) Huang, Wen Kai en_US dc.date (日期) 2010 en_US dc.date.accessioned 4-九月-2013 17:10:59 (UTC+8) - dc.date.available 4-九月-2013 17:10:59 (UTC+8) - dc.date.issued (上傳時間) 4-九月-2013 17:10:59 (UTC+8) - dc.identifier (其他 識別碼) G0987530161 en_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 (描述) 98753016 zh_TW dc.description (描述) 99 zh_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第一章 緒論 61.1 研究背景、動機 61.2 研究目標 61.3 研究貢獻 71.4 論文結構 7第二章 相關研究與技術背景 82.1 安全多方計算研究背景 82.2 安全多方計算協定介紹 82.3 安全雙方計算函式庫 92.4 用以安全多方計算之領域特定語言 10第三章 協定描述語言(PDL)與其運作環境之概要介紹 113.1 PDL語言介紹 113.2 PDL執行環境與流程： 153.3 PDL範例 20第四章 PDL之設計與實作 314.1 Secure Multiparty Computation Protocol 介紹 314.2 以PDL Data Description 建構之型態環境 324.3 Computation Description 設計 334.4 Compiler Construction 344.5 Properties of Code Generation of PDL 374.6 Code Generation Examples of the PDL Compiler 39第五章 PDL成果與性質討論 425.1 PDL語言討論：表達性與簡潔性 425.2 PDL Compiler對安全性分析的協助 455.3 抽象時間複雜度 47第六章 結論 496.1 本研究貢獻 496.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/#G0987530161 en_US dc.subject (關鍵詞) 安全多方計算 zh_TW dc.subject (關鍵詞) 隱私保護 zh_TW dc.subject (關鍵詞) 領域專屬語言 zh_TW dc.subject (關鍵詞) 靜態分析 zh_TW dc.subject (關鍵詞) Secure multi-party computation en_US dc.subject (關鍵詞) privacy protection en_US dc.subject (關鍵詞) domain-specific language en_US dc.subject (關鍵詞) static analysis en_US dc.title (題名) 安全多方計算協定描述語言之設計與實作 zh_TW dc.title (題名) A Protocol Description Language for Secure Multi-Party Computation en_US dc.type (資料類型) thesis en 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
