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 study on the design of Two-Party equality testing protocol and its applications
作者 吳承峰
Wu, Cheng Feng
貢獻者 左瑞麟
Tso, Ray Lin
吳承峰
Wu, Cheng Feng
關鍵詞 密碼學
ElGamal加密系統
同態加密
模糊傳輸
秘密計算
Cryptography
ElGamal encryption
Homomorphic encryption
Oblivious transfer
Secure computing
日期 2011
上傳時間 30-Oct-2012 11:28:21 (UTC+8)
摘要 雙方相等性驗證即是在不洩漏任何自身私密資訊的情況下，進行秘密計算來了解彼此的資訊是否相等。然而在大多數的現有協議之中，多數為不公平的協定，也就是說其中的一方(被告知方)只能相信另一方(告知方)所告知的比較結果，而無從驗證。雖然邱等學者在2011 年提出的〝具隱私保護功能之兩方相等性驗證機制之提案〞已經提供了具雙方驗證的協定，但此方案因為在加密演算法上的限制導致實作較為困難。因此，在本論文中，將利用ElGamal 的加密機制，提出了一套新的雙方相等性驗證的協議，具備相同的雙方相等性驗證的功能，但對加密演算法的限制較少，實作及運算也較為有效率。另外，搭配模糊傳輸的協定，讓使用者藉由本研究所提出的協定跟伺服器端溝通，來獲得所欲取得的資料，並同時保障使用者以及伺服器端的隱私。同時除了理論的證明安全性及正確性之外，也撰寫程式模擬並證實協定的正確性及討論其效能。
Two-party equality testing protocol allows two entities to compare their secrete information without leaking any information except the comparison result. In previous works, the comparison result can only be obtained by one entity (ie. informer) and then the entity informs the result to the other entity (ie. receiver). The receiver has to accept the received result since he has no way to verify its correctness. Ciou et al. in 2011 first mentioned this problem and proposed a new protocol to solve the aforementioned problem. However, their protocol has some specific restrictions which making it unpractical. In this paper, based on the ElGamal encryption, we propose a new two-party equality testing protocol. Our protocol has the same feature (ie. allows the two entries to test the correctness of the comparison result) as Ciou et al.’s protocol but is more efficient and practical than theirs. On the other hand, combining our protocol with an oblivious transfer protocol can let users communicate with servers and to get the data in a private way. It is useful on the issue of privacy protection. Finally, the security and correctness are discussed and proved. The efficiency of the protocol is also provided.
參考文獻 [1] J. Benaloh. “Dense probabilistic encryption”, Proceedings of the Workshop on Selected Areas of Cryptography, pp. 120–128, 1994.
[2] D. Boneh, EJ. Goh, and K. Nissim, “Evaluating 2-DNF formulas on ciphertexts”, Proceedings of Thepry of Cryptography (TCC), pp. 325–341, 2005.
[3] I. F. Blake and V. Kolesnikov, “Strong conditional oblivious transfer and computing on intervals”, Proceedings of Advances in Cryptology (Asiacrypt`04), LNCS vol.3329, pp.515-529, 2004.
[4] G. Brassard, C. Cre`peau, and J. M. Robert, “Oblivious transfer and privacy amplification”, Proceedings of Advances in Cryptology (Eurocrypt`97), LNCS vol.1233, pp. 334-346, 1997.
[5] M. Bellare, and S. Micali, “Non-interactive oblivious transfer”, Proceedings of Advances in Cryptology (Crypto`89), LNCS vol.435, pp. 547-557, 1990.
[6] S. F. Ciou, “Two-party equality test with privacy protection”, Master`s Thesis, 2011. (in Chinese)
[7] S. F. Ciou, R. Tso: “A privacy preserved two-party equality testing protocol”, Proceedings of ICGEC 2011, pp. 220-223, 2011.
[8] C. K. Chu and W. G. Tzeng, “Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries”, Proceedings of the Public Key Cryptography(PKC `05), LNCS vol.3386, pp.200-212, 2005.
[9] C. K. Chu and W. G. Tzeng, “Conditional oblivious cast”, Proceedings of the Public Key Cryptography (PKC `06), LNCS vol.3958, pp. 443-457, 2006.
[10] G. D. Crescenzo, R. Ostrovsky, and S. Rajagopalan, “Conditional oblivious transfer and time-released encryption”, Proceedings of Advances in Cryptology (Eurocrypt`99), LNCS vol.1592, pp. 74-89, 1999.
[11] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Trans. Inform. Theory, vol. 31, pp. 469-472, 1985.
[12] C. Gentry, “Fully homomorphic encryption using ideal lattices”, Proceedings of STOC ’09, ACM, pages 169–178, 2009.
[13] C. Gentry and Z. Ramzan, “Single-database private information retrieval with constant communication rate”, Proceedings of ICALP 2005, pp.803-815, 2005.
[14] S. Goldwasser and S. Micali, “Probabilistic encryption & how to play mental poker keeping secret all partial information”, Proceedings of Annual ACM Symposium on Theory of Computing, pp.365-377, 1982.
[15] B. Hemenway and R. Ostrovsky, “Lossy trapdoor functions from smooth homomorphic hash proof systems”, In Electronic Colloquium on Computational Complex-ity, Report TR09-127, 2009.
[16] M. Hirt and K. Sako, “Efficient receipt-Free voting based on homomorphic encryption”, Proceedings of (Eurocrypt`00), LNCS vol.1807, pp.539–556, 2000.
[17] K. Kurosawa and Q. Duong, “How to design efficient multiple-use 1-out-n oblivious
transfer”, IEICE Trans. Fundamentals, vol.E87-A, No.1, pp. 141-146, 2004.
[18] R. Li and C.K. Wu, “Co-operative private equality test”, International Journal of Network Security, vol.1, No.3, PP.149–153, 2005.
[19] N.Y. Lee and C.C. Wang, “Verifiable oblivious transfer protocol”, IEICE Trans. Information and Systems, vol.E88-D, No.12, pp. 2890-2892, 2005.
[20] M. Naor and B. Pinkas, “Efficient Oblivious Transfer Protocols”, Proceedings of ACM-SIAM symposium on Discrete algorithms, pp.448-457, 2000.
[21] P. Paillier, “Public-key cryptosystems based on composite degree residuocity classes”, Proceedings of Advances in Cryptology (Eurocrypt`99), LNCS vol.1592, pp. 223–238, 1999.
[22] R. Rivest, A. Shamir and L. Adleman,” A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM vol.21, pp. 120-126, 1977.
[23] M. Rabin, “How to exchange secrets by oblivious transfer”, Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981
[24] A. Yao, “Protocols for secure computations”, Proceedings of 21st Annual IEEE Symposium on Foundations of Computer Science, 1982.
描述 碩士
國立政治大學
資訊科學學系
99753035
100
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0099753035
資料類型 thesis
dc.contributor.advisor 左瑞麟zh_TW
dc.contributor.advisor Tso, Ray Linen_US
dc.contributor.author (Authors) 吳承峰zh_TW
dc.contributor.author (Authors) Wu, Cheng Fengen_US
dc.creator (作者) 吳承峰zh_TW
dc.creator (作者) Wu, Cheng Fengen_US
dc.date (日期) 2011en_US
dc.date.accessioned 30-Oct-2012 11:28:21 (UTC+8)-
dc.date.available 30-Oct-2012 11:28:21 (UTC+8)-
dc.date.issued (上傳時間) 30-Oct-2012 11:28:21 (UTC+8)-
dc.identifier (Other Identifiers) G0099753035en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54652-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 99753035zh_TW
dc.description (描述) 100zh_TW
dc.description.abstract (摘要) 雙方相等性驗證即是在不洩漏任何自身私密資訊的情況下，進行秘密計算來了解彼此的資訊是否相等。然而在大多數的現有協議之中，多數為不公平的協定，也就是說其中的一方(被告知方)只能相信另一方(告知方)所告知的比較結果，而無從驗證。雖然邱等學者在2011 年提出的〝具隱私保護功能之兩方相等性驗證機制之提案〞已經提供了具雙方驗證的協定，但此方案因為在加密演算法上的限制導致實作較為困難。因此，在本論文中，將利用ElGamal 的加密機制，提出了一套新的雙方相等性驗證的協議，具備相同的雙方相等性驗證的功能，但對加密演算法的限制較少，實作及運算也較為有效率。另外，搭配模糊傳輸的協定，讓使用者藉由本研究所提出的協定跟伺服器端溝通，來獲得所欲取得的資料，並同時保障使用者以及伺服器端的隱私。同時除了理論的證明安全性及正確性之外，也撰寫程式模擬並證實協定的正確性及討論其效能。zh_TW
dc.description.abstract (摘要) Two-party equality testing protocol allows two entities to compare their secrete information without leaking any information except the comparison result. In previous works, the comparison result can only be obtained by one entity (ie. informer) and then the entity informs the result to the other entity (ie. receiver). The receiver has to accept the received result since he has no way to verify its correctness. Ciou et al. in 2011 first mentioned this problem and proposed a new protocol to solve the aforementioned problem. However, their protocol has some specific restrictions which making it unpractical. In this paper, based on the ElGamal encryption, we propose a new two-party equality testing protocol. Our protocol has the same feature (ie. allows the two entries to test the correctness of the comparison result) as Ciou et al.’s protocol but is more efficient and practical than theirs. On the other hand, combining our protocol with an oblivious transfer protocol can let users communicate with servers and to get the data in a private way. It is useful on the issue of privacy protection. Finally, the security and correctness are discussed and proved. The efficiency of the protocol is also provided.en_US
dc.description.tableofcontents 1. 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 3
1.3 研究貢獻 4
1.4 論文架構 4
2. 背景知識與相關研究 5
2.1 同態加密 (Homomorphic Encryption) 5
2.2 ElGamal 加密演算法 8
2.3 祕密計算 (Secret Computation) 9
2.4 模糊傳輸 (Oblivious Transfer) 20
2.5 離散對數問題 (Discrete Logarithm Problem, DLP) 25
2.6 計算性迪菲-赫爾曼問題 (Computational Diffie-Hellman Problem, CDHP) 25
2.7 決定性迪菲-赫爾曼問題 (Decisional Diffie-Hellman Problem, DDHP) 26
2.8 語意安全 (Semantic Security) 26
3. 研究方法 29
3.1 基礎協定 29
3.2 雙方相等性驗證之協定 31
3.3 雙方相等性驗證搭配模糊傳輸之協定 35
4. 安全性分析 42
4.1 基礎協定安全性分析 42
4.2 雙方相等性驗證安全性分析 43
4.3 模糊傳輸安全性分析 48
5. 相關應用 50
5.1 登入驗證系統 50
5.2 線上購買數位化出版品 53
5.3 結合數位與現實的投票情境-核發選票 55
6. 實作與效能分析 57
7. 結論 62
參考文獻 63		zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0099753035en_US
dc.subject (關鍵詞) 密碼學zh_TW
dc.subject (關鍵詞) ElGamal加密系統zh_TW
dc.subject (關鍵詞) 同態加密zh_TW
dc.subject (關鍵詞) 模糊傳輸zh_TW
dc.subject (關鍵詞) 秘密計算zh_TW
dc.subject (關鍵詞) Cryptographyen_US
dc.subject (關鍵詞) ElGamal encryptionen_US
dc.subject (關鍵詞) Homomorphic encryptionen_US
dc.subject (關鍵詞) Oblivious transferen_US
dc.subject (關鍵詞) Secure computingen_US
dc.title (題名) 雙方相等性驗證機制的設計及其應用zh_TW
dc.title (題名) A study on the design of Two-Party equality testing protocol and its applicationsen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] J. Benaloh. “Dense probabilistic encryption”, Proceedings of the Workshop on Selected Areas of Cryptography, pp. 120–128, 1994.
[2] D. Boneh, EJ. Goh, and K. Nissim, “Evaluating 2-DNF formulas on ciphertexts”, Proceedings of Thepry of Cryptography (TCC), pp. 325–341, 2005.
[3] I. F. Blake and V. Kolesnikov, “Strong conditional oblivious transfer and computing on intervals”, Proceedings of Advances in Cryptology (Asiacrypt`04), LNCS vol.3329, pp.515-529, 2004.
[4] G. Brassard, C. Cre`peau, and J. M. Robert, “Oblivious transfer and privacy amplification”, Proceedings of Advances in Cryptology (Eurocrypt`97), LNCS vol.1233, pp. 334-346, 1997.
[5] M. Bellare, and S. Micali, “Non-interactive oblivious transfer”, Proceedings of Advances in Cryptology (Crypto`89), LNCS vol.435, pp. 547-557, 1990.
[6] S. F. Ciou, “Two-party equality test with privacy protection”, Master`s Thesis, 2011. (in Chinese)
[7] S. F. Ciou, R. Tso: “A privacy preserved two-party equality testing protocol”, Proceedings of ICGEC 2011, pp. 220-223, 2011.
[8] C. K. Chu and W. G. Tzeng, “Efficient k-out-of-n oblivious transfer schemes with adaptive and non-adaptive queries”, Proceedings of the Public Key Cryptography(PKC `05), LNCS vol.3386, pp.200-212, 2005.
[9] C. K. Chu and W. G. Tzeng, “Conditional oblivious cast”, Proceedings of the Public Key Cryptography (PKC `06), LNCS vol.3958, pp. 443-457, 2006.
[10] G. D. Crescenzo, R. Ostrovsky, and S. Rajagopalan, “Conditional oblivious transfer and time-released encryption”, Proceedings of Advances in Cryptology (Eurocrypt`99), LNCS vol.1592, pp. 74-89, 1999.
[11] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Trans. Inform. Theory, vol. 31, pp. 469-472, 1985.
[12] C. Gentry, “Fully homomorphic encryption using ideal lattices”, Proceedings of STOC ’09, ACM, pages 169–178, 2009.
[13] C. Gentry and Z. Ramzan, “Single-database private information retrieval with constant communication rate”, Proceedings of ICALP 2005, pp.803-815, 2005.
[14] S. Goldwasser and S. Micali, “Probabilistic encryption & how to play mental poker keeping secret all partial information”, Proceedings of Annual ACM Symposium on Theory of Computing, pp.365-377, 1982.
[15] B. Hemenway and R. Ostrovsky, “Lossy trapdoor functions from smooth homomorphic hash proof systems”, In Electronic Colloquium on Computational Complex-ity, Report TR09-127, 2009.
[16] M. Hirt and K. Sako, “Efficient receipt-Free voting based on homomorphic encryption”, Proceedings of (Eurocrypt`00), LNCS vol.1807, pp.539–556, 2000.
[17] K. Kurosawa and Q. Duong, “How to design efficient multiple-use 1-out-n oblivious
transfer”, IEICE Trans. Fundamentals, vol.E87-A, No.1, pp. 141-146, 2004.
[18] R. Li and C.K. Wu, “Co-operative private equality test”, International Journal of Network Security, vol.1, No.3, PP.149–153, 2005.
[19] N.Y. Lee and C.C. Wang, “Verifiable oblivious transfer protocol”, IEICE Trans. Information and Systems, vol.E88-D, No.12, pp. 2890-2892, 2005.
[20] M. Naor and B. Pinkas, “Efficient Oblivious Transfer Protocols”, Proceedings of ACM-SIAM symposium on Discrete algorithms, pp.448-457, 2000.
[21] P. Paillier, “Public-key cryptosystems based on composite degree residuocity classes”, Proceedings of Advances in Cryptology (Eurocrypt`99), LNCS vol.1592, pp. 223–238, 1999.
[22] R. Rivest, A. Shamir and L. Adleman,” A method for obtaining digital signatures and public-key cryptosystems”, Comm. ACM vol.21, pp. 120-126, 1977.
[23] M. Rabin, “How to exchange secrets by oblivious transfer”, Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981
[24] A. Yao, “Protocols for secure computations”, Proceedings of 21st Annual IEEE Symposium on Foundations of Computer Science, 1982.		zh_TW