學術產出-Theses
Article View/Open
Publication Export
-
題名 應用加法分持設計安全多方應用程式
Developing Secure Multiparty Applications Using Additive Secret Sharing作者 林子文 貢獻者 陳恭
林子文關鍵詞 安全多方計算
密碼學日期 2012 上傳時間 2-Sep-2013 16:49:01 (UTC+8) 摘要 資訊安全中,針對安全多方計算的問題已經發展了許多解法。其中一派以計算上安全(Computationally Secure)出發,嘗試對安全計算提出通用性(general)的解法 , 但 是 這 類 作 法 需 要 的 效 能 甚 鉅 。 另 外 一 派 是 以 資 訊 上 安 全 (Information-theoretically Secure)為前提,透過可信任的第三者公正伺服器來提供亂數資料輔助實際運作的兩方計算,這個方法雖然需要的效能比前者低,但是擴充成多方計算會造成設計的複雜度變高,一般實際的安全多方運用不見得需要這麼完整的解法。為了進一步推廣安全多方計算的運用,需要一個設計上較簡單,執行效率較高,在處理常用的安全多方計算時能套用或擴充的模型 (model),我們利用加法分持的概念設計了一個安全多方應用程式的模型,適合解決保障隱私的選舉投票的類似問題,並以安全會議排程為例,闡述如何考量安全多方計算的需求來應用這個模型。
Secure multiparty computation (SMC) allows several untrusting parties to conductcertain computations over their private data jointly without compromising their privacy.Since Yao`s pioneer work on secure two-party computation, there have been manyproposals of protocols for specific problems as well as of general approaches for secureprotocol development.However, those proposals, though general, are all very complex and take a lot ofcomputation resources, thus making people consider them impractical for real-worldapplications. This thesis focuses on a simple approach to secure multiparty computation,namely additive secret sharing, and presents a framework for developing somereal-world applications using it. We argue that, although this approach can solve only alimited scope of SMC problems, it is easy to apply and is computationally efficient.Besides showing some typical examples supported by our framework, we havedeveloped a secure meeting time scheduler to demonstrate the feasibility of thisapproach.參考文獻 [1] A. C. Yao. Protocols for secure computation. SFCS 1982: Proceedings of the 23rd Annual IEEESymposium 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 19thAnnual 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 ofComputer Science (FOCS’86), pages 162–167. IEEE, 1986.[4] Goldreich O, Secure multi-party computation (working draft). Available fromhttp://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 ACMConf. on Electronic Commerce, pages 129–139, 1999.[6] M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A.-R. Sadeghi, and T. Schneider. Secure evaluationof private linear branching programs with medical applications. In European Symposium on Researchin 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. In12th 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 Proceedingsof 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. ofPrivacy and Confidentiality, 1(1):59–98, 2009.[10] Du and M. J. Atallah. Secure multi-party computation problems and their applications: A reviewand 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 Advancesin Cryptology – EUROCRYPT’99, volume 1592 of LNCS, pages 223–238. Springer, 1999.[12] I. Damgard and M. Jurik. A generalisation, a simplification and some applications of paillier’sprobabilistic public-key system. In Public-Key Cryptography (PKC’01), volume 1992 of LNCS, pages119–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 the29th Annual ACM Symposium on Theory of Computing; 1997 May 4-6; El Paso, Texas, USA. NewYork, NY, USA: ACM Press; 1997. p. 446-55.[15] Du W, Zhan Z. A practical approach to solve Secure Multi-party Computation problems. NSPW2002: Proceedings of the 2002 Workshop on New Security Paradigms; 2002 Sep 23-26; VirginiaBeach, 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 TheoreticalAnalysis 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 onMachine Learning and Cybernetics, volume 5, pages 3006-3011, August 2007.[18] Wang IC, Chih-Hao Shen, Tsan-sheng Hsu, Churn-Jung Liau, Da-Wei Wang, andJustin 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, Kung Chen, Tsan-sheng Hsu, Liau CJ, Da-Wei Wang. An empirical study onprivacy and secure multi-party computation using exponentiation. Secure- Com 2009: InternationalSymposium on Secure Compu- ting; 2009 Aug 29-31; Vancouver, Canada. 2009. p. 182- 8.[20] Wang IC, Kung Chen, Tsan-sheng Hsu, Liau CJ, Shen CH, Da-Wei Wang. Protocols for securemulti- party computation: design, implementation and performance evaluation. Institute of InformationScience, Academia Sinica, Taiwan; 2009 Report No.: TR-IIS-09-005.[21] Wang IC, Kung Chen, J.H. Chuang, C.H. Lee, Tsan-sheng Hsu, Liau CJ, P.Y. Wang, and Da-WeiWang, “On Applying Secure Multi-party Computation: A Case Report”, Proc. of Asia-PacificAssociation Medical Informatics (APAMI 2009), Hiroshima, Japan, Nov. 22-24, 2009.[22] 疾病管制局,登革熱疾病飯擔之估計與應用,行政院衛生署疾病管制局 97 年度科技研究發展計畫。[23] Shamir, Adi (1979), How to Share a Secret, Communications of the ACM, Vol.22(11), 612-613 描述 碩士
國立政治大學
資訊科學學系
100753025
101資料來源 http://thesis.lib.nccu.edu.tw/record/#G0100753025 資料類型 thesis dc.contributor.advisor 陳恭 zh_TW dc.contributor.author (Authors) 林子文 zh_TW dc.creator (作者) 林子文 zh_TW dc.date (日期) 2012 en_US dc.date.accessioned 2-Sep-2013 16:49:01 (UTC+8) - dc.date.available 2-Sep-2013 16:49:01 (UTC+8) - dc.date.issued (上傳時間) 2-Sep-2013 16:49:01 (UTC+8) - dc.identifier (Other Identifiers) G0100753025 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/59442 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 100753025 zh_TW dc.description (描述) 101 zh_TW dc.description.abstract (摘要) 資訊安全中,針對安全多方計算的問題已經發展了許多解法。其中一派以計算上安全(Computationally Secure)出發,嘗試對安全計算提出通用性(general)的解法 , 但 是 這 類 作 法 需 要 的 效 能 甚 鉅 。 另 外 一 派 是 以 資 訊 上 安 全 (Information-theoretically Secure)為前提,透過可信任的第三者公正伺服器來提供亂數資料輔助實際運作的兩方計算,這個方法雖然需要的效能比前者低,但是擴充成多方計算會造成設計的複雜度變高,一般實際的安全多方運用不見得需要這麼完整的解法。為了進一步推廣安全多方計算的運用,需要一個設計上較簡單,執行效率較高,在處理常用的安全多方計算時能套用或擴充的模型 (model),我們利用加法分持的概念設計了一個安全多方應用程式的模型,適合解決保障隱私的選舉投票的類似問題,並以安全會議排程為例,闡述如何考量安全多方計算的需求來應用這個模型。 zh_TW dc.description.abstract (摘要) Secure multiparty computation (SMC) allows several untrusting parties to conductcertain computations over their private data jointly without compromising their privacy.Since Yao`s pioneer work on secure two-party computation, there have been manyproposals of protocols for specific problems as well as of general approaches for secureprotocol development.However, those proposals, though general, are all very complex and take a lot ofcomputation resources, thus making people consider them impractical for real-worldapplications. This thesis focuses on a simple approach to secure multiparty computation,namely additive secret sharing, and presents a framework for developing somereal-world applications using it. We argue that, although this approach can solve only alimited scope of SMC problems, it is easy to apply and is computationally efficient.Besides showing some typical examples supported by our framework, we havedeveloped a secure meeting time scheduler to demonstrate the feasibility of thisapproach. en_US dc.description.tableofcontents 第一章 緒論.......................................................................41.1 研究背景、動機................................................................41.2 研究目標...................................................................51.3 研究貢獻...................................................................51.4 論文結構...................................................................5第二章 相關研究與技術背景.........................................................62.1 安全多方計算研究背景.......................................................62.2 安全多方計算協定介紹與比較.................................................72.2.1 計算上安全的多方計算協定...............................................72.2.2 資訊理論上安全的多方計算協定...........................................8第三章 系統架構..................................................................113.1 加法分持計算系統介紹......................................................113.2 加法分持系統執行範例......................................................153.2.1 百萬富翁問題..........................................................153.2.2 安全計算多人資產總和..................................................183.2.3保障隱私的權重投票...................................................213.2.4 健保局與疾管局合作之登革熱研究........................................23第四章 安全會議時間排程..........................................................274.1 使用情境..................................................................274.2 和其他排程網站的差異......................................................294.3 安全會議時間排程演算法....................................................29第五章 成果與討論................................................................335.1 實作環境與成果............................................................335.2 適合用加法分持計算系統解決的問題..........................................33第六章 結論......................................................................376.1 本研究貢獻................................................................376.2 未來研究..................................................................376.2.1 乘法分持..............................................................376.2.2 浮點數運算............................................................386.2.3 更複雜的計算步驟......................................................396.2.4 平行化的計算..........................................................40附錄.............................................................................43一、加法分持計算系統的範例....................................................431. 加法分持計算系統 — 兩方資料加總.........................................432. 加法分持計算系統 — 三方資料加總.........................................443. 加法分持計算系統 — 減法.................................................454. 加法分持計算系統 — 權重計算.............................................465. 加法分持計算系統 — And 邏輯運算 ........................................476. 加法分持計算系統 — Or 邏輯運算..........................................487. 加法分持計算系統 — XOR 邏輯運算.........................................49二、實驗工具資訊..............................................................50 zh_TW dc.format.extent 1048539 bytes - dc.format.mimetype application/pdf - dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0100753025 en_US dc.subject (關鍵詞) 安全多方計算 zh_TW dc.subject (關鍵詞) 密碼學 zh_TW dc.title (題名) 應用加法分持設計安全多方應用程式 zh_TW dc.title (題名) Developing Secure Multiparty Applications Using Additive Secret Sharing en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] A. C. Yao. Protocols for secure computation. SFCS 1982: Proceedings of the 23rd Annual IEEESymposium 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 19thAnnual 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 ofComputer Science (FOCS’86), pages 162–167. IEEE, 1986.[4] Goldreich O, Secure multi-party computation (working draft). Available fromhttp://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 ACMConf. on Electronic Commerce, pages 129–139, 1999.[6] M. Barni, P. Failla, V. Kolesnikov, R. Lazzeretti, A.-R. Sadeghi, and T. Schneider. Secure evaluationof private linear branching programs with medical applications. In European Symposium on Researchin 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. In12th 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 Proceedingsof 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. ofPrivacy and Confidentiality, 1(1):59–98, 2009.[10] Du and M. J. Atallah. Secure multi-party computation problems and their applications: A reviewand 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 Advancesin Cryptology – EUROCRYPT’99, volume 1592 of LNCS, pages 223–238. Springer, 1999.[12] I. Damgard and M. Jurik. A generalisation, a simplification and some applications of paillier’sprobabilistic public-key system. In Public-Key Cryptography (PKC’01), volume 1992 of LNCS, pages119–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 the29th Annual ACM Symposium on Theory of Computing; 1997 May 4-6; El Paso, Texas, USA. NewYork, NY, USA: ACM Press; 1997. p. 446-55.[15] Du W, Zhan Z. A practical approach to solve Secure Multi-party Computation problems. NSPW2002: Proceedings of the 2002 Workshop on New Security Paradigms; 2002 Sep 23-26; VirginiaBeach, 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 TheoreticalAnalysis 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 onMachine Learning and Cybernetics, volume 5, pages 3006-3011, August 2007.[18] Wang IC, Chih-Hao Shen, Tsan-sheng Hsu, Churn-Jung Liau, Da-Wei Wang, andJustin 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, Kung Chen, Tsan-sheng Hsu, Liau CJ, Da-Wei Wang. An empirical study onprivacy and secure multi-party computation using exponentiation. Secure- Com 2009: InternationalSymposium on Secure Compu- ting; 2009 Aug 29-31; Vancouver, Canada. 2009. p. 182- 8.[20] Wang IC, Kung Chen, Tsan-sheng Hsu, Liau CJ, Shen CH, Da-Wei Wang. Protocols for securemulti- party computation: design, implementation and performance evaluation. Institute of InformationScience, Academia Sinica, Taiwan; 2009 Report No.: TR-IIS-09-005.[21] Wang IC, Kung Chen, J.H. Chuang, C.H. Lee, Tsan-sheng Hsu, Liau CJ, P.Y. Wang, and Da-WeiWang, “On Applying Secure Multi-party Computation: A Case Report”, Proc. of Asia-PacificAssociation Medical Informatics (APAMI 2009), Hiroshima, Japan, Nov. 22-24, 2009.[22] 疾病管制局,登革熱疾病飯擔之估計與應用,行政院衛生署疾病管制局 97 年度科技研究發展計畫。[23] Shamir, Adi (1979), How to Share a Secret, Communications of the ACM, Vol.22(11), 612-613 zh_TW
