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

題名 應用加法分持設計安全多方應用程式
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 conduct
certain computations over their private data jointly without compromising their privacy.
Since Yao`s pioneer work on secure two-party computation, there have been many
proposals of protocols for specific problems as well as of general approaches for secure
protocol development.
However, those proposals, though general, are all very complex and take a lot of
computation resources, thus making people consider them impractical for real-world
applications. This thesis focuses on a simple approach to secure multiparty computation,
namely additive secret sharing, and presents a framework for developing some
real-world applications using it. We argue that, although this approach can solve only a
limited scope of SMC problems, it is easy to apply and is computationally efficient.
Besides showing some typical examples supported by our framework, we have
developed a secure meeting time scheduler to demonstrate the feasibility of this
approach.
參考文獻 [1] A. 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] 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. Damgard and M. 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] 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] Wang IC, 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, Kung Chen, Tsan-sheng Hsu, Liau CJ, Da-Wei Wang. 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, Kung Chen, Tsan-sheng Hsu, Liau CJ, Shen CH, Da-Wei Wang. 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] Wang IC, Kung Chen, J.H. Chuang, C.H. Lee, Tsan-sheng Hsu, Liau CJ, P.Y. Wang, and Da-Wei
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.
[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 (日期) 2012en_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) G0100753025en_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 (描述) 100753025zh_TW
dc.description (描述) 101zh_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 conduct
certain computations over their private data jointly without compromising their privacy.
Since Yao`s pioneer work on secure two-party computation, there have been many
proposals of protocols for specific problems as well as of general approaches for secure
protocol development.
However, those proposals, though general, are all very complex and take a lot of
computation resources, thus making people consider them impractical for real-world
applications. This thesis focuses on a simple approach to secure multiparty computation,
namely additive secret sharing, and presents a framework for developing some
real-world applications using it. We argue that, although this approach can solve only a
limited scope of SMC problems, it is easy to apply and is computationally efficient.
Besides showing some typical examples supported by our framework, we have
developed a secure meeting time scheduler to demonstrate the feasibility of this
approach.		en_US
dc.description.tableofcontents 第一章 緒論.......................................................................4
1.1 研究背景、動機................................................................4
1.2 研究目標...................................................................5
1.3 研究貢獻...................................................................5
1.4 論文結構...................................................................5
第二章 相關研究與技術背景.........................................................6
2.1 安全多方計算研究背景.......................................................6
2.2 安全多方計算協定介紹與比較.................................................7
2.2.1 計算上安全的多方計算協定...............................................7
2.2.2 資訊理論上安全的多方計算協定...........................................8
第三章 系統架構..................................................................11
3.1 加法分持計算系統介紹......................................................11
3.2 加法分持系統執行範例......................................................15
3.2.1 百萬富翁問題..........................................................15
3.2.2 安全計算多人資產總和..................................................18
3.2.3
保障隱私的權重投票...................................................21
3.2.4 健保局與疾管局合作之登革熱研究........................................23
第四章 安全會議時間排程..........................................................27
4.1 使用情境..................................................................27
4.2 和其他排程網站的差異......................................................29
4.3 安全會議時間排程演算法....................................................29
第五章 成果與討論................................................................33
5.1 實作環境與成果............................................................33
5.2 適合用加法分持計算系統解決的問題..........................................33
第六章 結論......................................................................37
6.1 本研究貢獻................................................................37
6.2 未來研究..................................................................37
6.2.1 乘法分持..............................................................37
6.2.2 浮點數運算............................................................38
6.2.3 更複雜的計算步驟......................................................39
6.2.4 平行化的計算..........................................................40
附錄.............................................................................43
一、加法分持計算系統的範例....................................................43
1. 加法分持計算系統 — 兩方資料加總.........................................43
2. 加法分持計算系統 — 三方資料加總.........................................44
3. 加法分持計算系統 — 減法.................................................45
4. 加法分持計算系統 — 權重計算.............................................46
5. 加法分持計算系統 — And 邏輯運算 ........................................47
6. 加法分持計算系統 — Or 邏輯運算..........................................48
7. 加法分持計算系統 — 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/#G0100753025en_US
dc.subject (關鍵詞) 安全多方計算zh_TW
dc.subject (關鍵詞) 密碼學zh_TW
dc.title (題名) 應用加法分持設計安全多方應用程式zh_TW
dc.title (題名) Developing Secure Multiparty Applications Using Additive Secret Sharingen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] A. 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] 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. Damgard and M. 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] 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] Wang IC, 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, Kung Chen, Tsan-sheng Hsu, Liau CJ, Da-Wei Wang. 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, Kung Chen, Tsan-sheng Hsu, Liau CJ, Shen CH, Da-Wei Wang. 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] Wang IC, Kung Chen, J.H. Chuang, C.H. Lee, Tsan-sheng Hsu, Liau CJ, P.Y. Wang, and Da-Wei
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.
[22] 疾病管制局,登革熱疾病飯擔之估計與應用,行政院衛生署疾病管制局 97 年度科技研究發
展計畫。
[23] Shamir, Adi (1979), How to Share a Secret, Communications of the ACM, Vol.22(11), 612-613		zh_TW