Publications-Theses
Article View/Open
Publication Export
-
題名 基於同態加密的相等性驗證之通用架構設計
Generic Construction on Equality Test Based on Homomorphic Encryptions作者 周為涵
Chou, Wei-Han貢獻者 左瑞麟
周為涵
Chou, Wei-Han關鍵詞 同態加密
秘密計算
相等性驗證日期 2018 上傳時間 12-Feb-2019 16:00:16 (UTC+8) 摘要 雙方相等性驗證是指在不洩漏任何自身私密資訊的情況下，進行秘密計算來了解彼此的資訊是否相等。然而在大多數現有協議中，多數為不公平的協定，也就是說其中的一方(被告知方)只能相信另一方(告知方)所告知的比較結果而無從驗證。雖然已有學者提出了一些可以雙方驗證的提案機制，但是這些協議或因加密演算法限制導致實作困難，或因必須使用指定加密演算法限制導致協定彈性較低。因此，在本論文中，將提出一套新的雙方相等性驗證的協議，具備相同的雙方相等性驗證的功能，但對加密演算法限制較低，適用於所有可多次進行同態運算的加法同態加密演算法或乘法同態加密演算法，實作及運算也較為有效率。提出協議後，再以理論證明協議的安全性及正確性，並提出該協議的相關應用，最後分析協議的時間複雜度及討論其效能。
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. Although some scholars have proposed some proposal mechanisms that can be verified by both parties, Those protocols may be difficult to implement due to limitations of the encryption algorithm, or the contract flexibility may be low due to the necessity of using the specified encryption algorithm. Therefore, in this thesis,we propose a new two-party equality testing protocol. Our protocol has the same function of mutual equality verification, but has lower restrictions on the encryption algorithm and is applicable to almost all Addition homomorphic encryption algorithm or multiplicative homomorphic encryption algorithm. It is also more efficient in implementation and operation. After the agreement is proposed, the security and correctness of the protocol are proved by theory, and the related applications of the protocol are proposed. Finally, the time complexity of the protocol is analyzed and its performance is discussed.參考文獻 [1] Andrew C. Yao, "Protocols for Secure Computations", Proceedings of 21stAnnual IEEE Symposium on Foundations of Computer Science, 1982.[2]T. ElGamal, “ A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Trans. Inform. Theory, vol. 31, pp. 469-472, 1985.[3] Pascal Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes”, Proceedings of Advances in Cryptology (Eurocrypt’99), LNCS vol. 1592, pp.l 223-238, 1999.[4]C.Gentry, "Fully homomorphic encryption using ideal lattices", Proceedings of STOC ‘09, ACM, pages 169-178, 2009.[5] 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.[6] R. Li and C.K. Wu, "Co-operatice private equality test", International Journal of Network Security, vol.1 No.3, PP.149-153, 2005.[7] Cheng-Feng Wu, "A Study on the Design of Two-Party Equality Testing Protocol and Its Applications"[8] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal on Computing, Vol. 26, No. 5, pp. 1484-1509, 1997[9] Peter Mell and Tim Grance, “The NIST Definition of Cloud Computing”[10] J. Benaloh, “Dense Probabilistic encryption”, Proceedings of the Workshop on Selected Areas of Cryptography, pp. 120-128, 1994.[11] 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.[12] D. Boneh, EJ. Goh, and K. Nissim, “Evaluating 2-DNF formulas on ciphertexts”, Proceedings of Thepry of Cryptography (TCC), pp. 325-341, 2005.[13] M. Hirt and K. Sako, “Efficient receipt-Free voting based on homomorphic encryption”, Proceedings of (Eurocrypt’00), LNCS vol. 1807, pp.539-556, 2000.[14] B. Hemenway and R. Ostrovsky, “Lossy trapdoor functions from smooth homomorphic hasgh proof systems”, In Electronic Colloquium on Computational Complexity, Report TR09-127, 2009.[15] C. Gentry and Z. Ramzan, “Single-database private information retrieval with constant communication rate”, Proceedings of ICALP 2005, pp.803-815, 2005.[16] J. Bernstein and Tenja Lange, “Post-Quantum cryptography”, Nature 549, 188-194, 2017.[17] S. F. Ciou, “Two-party equality test with privacy protection”, Master’s Thesis, 2011. (in Chinese)[18] S. F. Ciou, R.Tso, “A privacy preserved two-party equality testing protocol”, Proceedings of ICGEC 2011, pp. 220-223, 2011.[19] Naoki Ogura, Go Yamamoto, Tetsutaro Kobayashi, Shigenori Uchiyama, “An Improvement of Key Generation Algorithm for Gentry’s Homomorphic Encryption Scheme” International Workshop on Security(IWSEC 2010). Pp. 70-83, 2010.[20] Peter Scholl and Nigel P. Smart, “Improved key generation for Gentry’s fully homomorphic encryption scheme”, IMACC’11, pp.10-22, 2011.[21] Craig Gentry and Shai Halevi, ”Implementing Gentry’s Fully-Homomorphic Encryption Scheme” Proceedings of Advances in Cryptology (Eurocrypt’2011) pp.129-148 描述 碩士
國立政治大學
資訊科學系碩士在職專班
104971004資料來源 http://thesis.lib.nccu.edu.tw/record/#G0104971004 資料類型 thesis dc.contributor.advisor 左瑞麟 zh_TW dc.contributor.author (Authors) 周為涵 zh_TW dc.contributor.author (Authors) Chou, Wei-Han en_US dc.creator (作者) 周為涵 zh_TW dc.creator (作者) Chou, Wei-Han en_US dc.date (日期) 2018 en_US dc.date.accessioned 12-Feb-2019 16:00:16 (UTC+8) - dc.date.available 12-Feb-2019 16:00:16 (UTC+8) - dc.date.issued (上傳時間) 12-Feb-2019 16:00:16 (UTC+8) - dc.identifier (Other Identifiers) G0104971004 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/122332 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系碩士在職專班 zh_TW dc.description (描述) 104971004 zh_TW dc.description.abstract (摘要) 雙方相等性驗證是指在不洩漏任何自身私密資訊的情況下，進行秘密計算來了解彼此的資訊是否相等。然而在大多數現有協議中，多數為不公平的協定，也就是說其中的一方(被告知方)只能相信另一方(告知方)所告知的比較結果而無從驗證。雖然已有學者提出了一些可以雙方驗證的提案機制，但是這些協議或因加密演算法限制導致實作困難，或因必須使用指定加密演算法限制導致協定彈性較低。因此，在本論文中，將提出一套新的雙方相等性驗證的協議，具備相同的雙方相等性驗證的功能，但對加密演算法限制較低，適用於所有可多次進行同態運算的加法同態加密演算法或乘法同態加密演算法，實作及運算也較為有效率。提出協議後，再以理論證明協議的安全性及正確性，並提出該協議的相關應用，最後分析協議的時間複雜度及討論其效能。 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. Although some scholars have proposed some proposal mechanisms that can be verified by both parties, Those protocols may be difficult to implement due to limitations of the encryption algorithm, or the contract flexibility may be low due to the necessity of using the specified encryption algorithm. Therefore, in this thesis,we propose a new two-party equality testing protocol. Our protocol has the same function of mutual equality verification, but has lower restrictions on the encryption algorithm and is applicable to almost all Addition homomorphic encryption algorithm or multiplicative homomorphic encryption algorithm. It is also more efficient in implementation and operation. After the agreement is proposed, the security and correctness of the protocol are proved by theory, and the related applications of the protocol are proposed. Finally, the time complexity of the protocol is analyzed and its performance is discussed. en_US dc.description.tableofcontents 1 緒論 11.1研究背景 11.2研究動機與目的 11.3研究貢獻 21.4論文架構 32 背景知識 42.1 ElGamal加密演算法 42.2 Paillier加密演算法 42.3同態加密 42.4 加法同態加密 52.5乘法同態加密 52.6 雙重加密演算法 62.7 語意安全 63 既有秘密計算相等性驗證協定 73.1李姓學者與武姓學者的協定 73.2邱姓學者的協定 83.3吳的協定 94雙方相等性驗證協定 114.1基礎協定 114.2基礎協定討論 194.3雙方相等性驗證協定 195 安全性分析 325.1假設Alice為攻擊者 325.2假設Bob為攻擊者 326 相關應用討論 346.1登入驗證系統 346.2線上刷卡驗證系統 357時間複雜度分析 387.1基礎協定的時間複雜度 387.2雙方相等性驗證協定的時間複雜度 388 結論 39 zh_TW dc.format.extent 1552999 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0104971004 en_US dc.subject (關鍵詞) 同態加密 zh_TW dc.subject (關鍵詞) 秘密計算 zh_TW dc.subject (關鍵詞) 相等性驗證 zh_TW dc.title (題名) 基於同態加密的相等性驗證之通用架構設計 zh_TW dc.title (題名) Generic Construction on Equality Test Based on Homomorphic Encryptions en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Andrew C. Yao, "Protocols for Secure Computations", Proceedings of 21stAnnual IEEE Symposium on Foundations of Computer Science, 1982.[2]T. ElGamal, “ A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Trans. Inform. Theory, vol. 31, pp. 469-472, 1985.[3] Pascal Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes”, Proceedings of Advances in Cryptology (Eurocrypt’99), LNCS vol. 1592, pp.l 223-238, 1999.[4]C.Gentry, "Fully homomorphic encryption using ideal lattices", Proceedings of STOC ‘09, ACM, pages 169-178, 2009.[5] 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.[6] R. Li and C.K. Wu, "Co-operatice private equality test", International Journal of Network Security, vol.1 No.3, PP.149-153, 2005.[7] Cheng-Feng Wu, "A Study on the Design of Two-Party Equality Testing Protocol and Its Applications"[8] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal on Computing, Vol. 26, No. 5, pp. 1484-1509, 1997[9] Peter Mell and Tim Grance, “The NIST Definition of Cloud Computing”[10] J. Benaloh, “Dense Probabilistic encryption”, Proceedings of the Workshop on Selected Areas of Cryptography, pp. 120-128, 1994.[11] 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.[12] D. Boneh, EJ. Goh, and K. Nissim, “Evaluating 2-DNF formulas on ciphertexts”, Proceedings of Thepry of Cryptography (TCC), pp. 325-341, 2005.[13] M. Hirt and K. Sako, “Efficient receipt-Free voting based on homomorphic encryption”, Proceedings of (Eurocrypt’00), LNCS vol. 1807, pp.539-556, 2000.[14] B. Hemenway and R. Ostrovsky, “Lossy trapdoor functions from smooth homomorphic hasgh proof systems”, In Electronic Colloquium on Computational Complexity, Report TR09-127, 2009.[15] C. Gentry and Z. Ramzan, “Single-database private information retrieval with constant communication rate”, Proceedings of ICALP 2005, pp.803-815, 2005.[16] J. Bernstein and Tenja Lange, “Post-Quantum cryptography”, Nature 549, 188-194, 2017.[17] S. F. Ciou, “Two-party equality test with privacy protection”, Master’s Thesis, 2011. (in Chinese)[18] S. F. Ciou, R.Tso, “A privacy preserved two-party equality testing protocol”, Proceedings of ICGEC 2011, pp. 220-223, 2011.[19] Naoki Ogura, Go Yamamoto, Tetsutaro Kobayashi, Shigenori Uchiyama, “An Improvement of Key Generation Algorithm for Gentry’s Homomorphic Encryption Scheme” International Workshop on Security(IWSEC 2010). Pp. 70-83, 2010.[20] Peter Scholl and Nigel P. Smart, “Improved key generation for Gentry’s fully homomorphic encryption scheme”, IMACC’11, pp.10-22, 2011.[21] Craig Gentry and Shai Halevi, ”Implementing Gentry’s Fully-Homomorphic Encryption Scheme” Proceedings of Advances in Cryptology (Eurocrypt’2011) pp.129-148 zh_TW dc.identifier.doi (DOI) 10.6814/THE.NCCU.EMCS.001.2019.B02 en_US
