請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56805完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 吳家麟(Ja-Lin Wu) | |
| dc.contributor.author | Tzu-Hsiang Kuo | en |
| dc.contributor.author | 郭子翔 | zh_TW |
| dc.date.accessioned | 2021-06-16T05:49:35Z | - |
| dc.date.available | 2020-08-04 | |
| dc.date.copyright | 2020-08-04 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-07-25 | |
| dc.identifier.citation | [1] T. Veugen, F. Blom, S. J. A. de Hoogh, and Z. Erkin, “Secure comparison protocols in the semi-honest model,” IEEE Journal of Selected Topics in Signal Processing, vol. 9, no. 7, pp. 1217–1228, 2015. 2 [2] I. Damgard, M. Geisler, and M. Krøigaard, “Homomorphic encryption and secure comparison,” IJACT, vol. 1, pp. 22–31, 02 2008. 2, 3, 47 [3] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in International conference on the theory and applications of cryptographic techniques. Springer, 1999, pp. 223–238. 2 [4] I. Damgard, M. Geisler, and M. Krøigaard, “A correction to ’efficient and secure comparison for on-line auctions’,” IJACT, vol. 1, no. 4, pp. 323–324, 2009. [Online]. Available: https://doi.org/10.1504/IJACT.2009.028031 2, 3, 47 [5] J. Groth, “Cryptography in subgroups of Z∗n,” in Theory of Cryptography Conference. Springer, 2005, pp. 50–65. 2, 47, 48, 49 [6] R. A. Carlton, “Secure integer comparisons using the homomorphic properties of prime power subgroups,” Ph.D. dissertation, The University of Western Ontario, 2017. 2, 3 [7] R. Carlton, A. Essex, and K. Kapulkin, “Threshold properties of prime power subgroups with application to secure integer comparisons,” in Cryptographers’ Track at the RSA Conference. Springer, 2018, pp. 137–156. 2, 3, 47, 48, 49, 51, 53 [8] I. Damgard, M. Geisler, and M. Krøigaard, “Efficient and secure comparison for on-line auctions,” in Information Security and Privacy, 12th Australasian Conference, ACISP 2007, Townsville, Australia, July 2-4, 2007, Proceedings, ser. Lecture Notes in Computer Science, J. Pieprzyk, H. Ghodosi, and E. Dawson, Eds., vol. 4586. Springer, 2007, pp. 416–430. [Online]. Available: https://doi.org/10.1007/978-3-540-73458-1 30 3 [9] T. Veugen, “Improving the dgk comparison protocol,” in 2012 IEEE International Workshop on Information Forensics and Security (WIFS). IEEE, 2012, pp. 49–54. 3 [10] ——, “Correction to” improving the dgk comparison protocol”.” IACR Cryptology ePrint Archive, vol. 2018, p. 1100, 2018. 3, 51, 53 [11] C. Gentry and D. Boneh, A fully homomorphic encryption scheme. Stanford university Stanford, 2009, vol. 20, no. 9. 4, 7 [12] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 169–178. 4 [13] M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2010, pp. 24–43. 4 [14] Z. Brakerski and V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) lwe,” in Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, ser. FOCS ’11. USA: IEEE Computer Society, 2011, p. 97–106. [Online]. Available: https://doi.org/10.1109/FOCS.2011.12 4 [15] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ser. ITCS ’12. New York, NY, USA: Association for Computing Machinery, 2012, p. 309–325. [Online]. Available: https://doi.org/10.1145/2090236.2090262 4, 7 [16] Z. Brakerski, “Fully homomorphic encryption without modulus switching from classical gapsvp,” in Annual Cryptology Conference. Springer, 2012, pp. 868–886. 4 [17] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption.” IACR Cryptology ePrint Archive, vol. 2012, p. 144, 2012. 4, 7 [18] C. Gentry, A. Sahai, and B. Waters, “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based,” in Annual Cryptology Conference. Springer, 2013, pp. 75–92. 4 [19] J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2017, pp. 409–437. 4 [20] Z. Brakerski and V. Vaikuntanathan, “Fully homomorphic encryption from ring-lwe and security for key dependent messages,” in Annual cryptology conference. Springer, 2011, pp. 505–524. 4 [21] M. Huo, K. Wu, and Q. Ye, “A note on lower digits extraction polynomial for bootstrapping,” arXiv preprint arXiv:1906.02867, 2019. 7 [22] V. Lyubashevsky, C. Peikert, and O. Regev, “On ideal lattices and learning with errors over rings,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2010, pp. 1–23. 10 [23] “Microsoft SEAL (release 3.4),” https://github.com/Microsoft/SEAL, Oct. 2019, microsoft Research, Redmond, WA. 10 [24] M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, and V. Vaikuntanathan, “Homomorphic encryption security standard,” HomomorphicEncryption.org, Toronto, Canada, Tech. Rep., November 2018. 56 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56805 | - |
| dc.description.abstract | 假設涉事雙方分別握有一個位元的整數(即其大小介於0到2 − 1之間)，本文關切之安全比較的目標是：在不洩露各自整數的前提下計算出兩數字的大小關係。 現存較快的安全比較協議都是基於同態加密技術，而大部分基於同態加密的安全比較協議，至少需要加密 其中一方的各個位元。意即每位元至少需要一次加密的時間，這形成一個(時間)效能瓶頸。 在本論文中，我們使用 BFV 加密技術以改善 DGK 安全比較協議，並用批次處理技巧來減少協議中所需的加密次數。舉例來說，我們提出的演算法總共只需要六次加密(並不會隨著 l 的大小增減)。令為事先選定之安全參數，我們可以達到̃( + )的時間複雜度。實驗中我們可在十三毫秒內完成四零九六位元的安全比較，(時間)效能約為現存基於同態加密技術最快安全比較協議的兩百八十倍。 | zh_TW |
| dc.description.abstract | Secure comparison is a fundamental problem in multiparty computation. Assume there are two different parties, each of them holds an l-bit integer, denoted by a and b respectively. The goal of secure comparison is to compute the order relationship between a and b, say (a ≥ b) ∈ {0, 1}, without revealing their inputs to any others. The fastest solution to secure comparison (so far) is based on homomorphic encryption. Since previous solutions based on homomorphic encryption need at least Ω(l) encryptions for each l-bit comparison, the total encryption time leads to a computational bottleneck for these protocols. In this thesis, we present a fast, semi-honest secure comparison protocol based on BFV encryption scheme. With the vector-like plaintext space of BFV scheme, the number of required encryptions can be significantly reduced; actually, only six encryptions are needed for each comparison in our protocol. In other words, the proposed protocol can achieve the time complexity O˜(λ + l) for a given security parameter λ. As a result, 4096-bit integers can be securely compared within 12.08ms, which is 280 times faster than the state-of-the-art homomorphic encryption-based secure comparison protocol. Furthermore, we can compare k pairs of l/k-bit integers with almost the same execution time to comparing l-bit integers, and achieve higher throughput regardless of the compared integer-size. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T05:49:35Z (GMT). No. of bitstreams: 1 U0001-2307202021062800.pdf: 1099586 bytes, checksum: a5f1e4d321125bc6d4ab634c45efe5eb (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | Abstract i List of Figures vii List of Tables ix 1 Introduction 1 1.1 Secure Comparison . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 BFV Encryption Scheme . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Secure Decryption . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Paper Organization . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 BFV Encryption 7 2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 Quotient Ring . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 Distribution and Sampling . . . . . . . . . . . . . . . . . 9 2.2 Security Assumption . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Symmetric Encryption and Decryption . . . . . . . . . . . . . . . 11 2.5 Homomorphic Operations . . . . . . . . . . . . . . . . . . . . . 13 2.6 Public Key Generation and Encryption . . . . . . . . . . . . . . . 17 2.7 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.8 Batching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.8.1 Parameter Setting . . . . . . . . . . . . . . . . . . . . . . 20 2.8.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . 21 3 Two-Party Computation and BFV Encryption 25 3.1 Secure Decryption . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Separate Decryption . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 Two Party Computation via BFV Scheme . . . . . . . . . . . . . 34 4 A High Throughput, Semi-Honest, Secure Comparison Protocol 37 4.1 Improving DGK Secure Comparison Protocol via BFV Scheme . 37 4.2 High Throughput Comparison Protocol . . . . . . . . . . . . . . 40 4.2.1 Single Pair Integer Comparison . . . . . . . . . . . . . . 40 4.2.2 Compare Pairs of Integers Simultaneously . . . . . . . . . 42 5 Experiment Results 47 5.1 Encryption Schemes . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2.1 Computational Cost . . . . . . . . . . . . . . . . . . . . 49 5.2.2 Communication Cost . . . . . . . . . . . . . . . . . . . . 52 5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6 Conclusion 55 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Reference 57 | |
| dc.language.iso | en | |
| dc.subject | 環容錯 | zh_TW |
| dc.subject | 安全比較協議 | zh_TW |
| dc.subject | 安全拍賣 | zh_TW |
| dc.subject | 全同態加密 | zh_TW |
| dc.subject | 安全多方運算 | zh_TW |
| dc.subject | ring learning with error | en |
| dc.subject | secure comparison | en |
| dc.subject | multi-party computation | en |
| dc.subject | fully homomorphic encryption | en |
| dc.subject | secure auction | en |
| dc.title | 一個基於BFV加密的高通量安全比較協議 | zh_TW |
| dc.title | A High Throughput BFV-based Secure Comparison Protocol | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 曾維新(WEI-XIN ZENG),陳祝嵩(Chu-Song Chen),黃俊翔(Chun-Hsiang Huang),陳駿丞(Jun-Cheng Chen) | |
| dc.subject.keyword | 安全比較協議,安全多方運算,全同態加密,安全拍賣,環容錯, | zh_TW |
| dc.subject.keyword | secure comparison,multi-party computation,fully homomorphic encryption,secure auction,ring learning with error, | en |
| dc.relation.page | 61 | |
| dc.identifier.doi | 10.6342/NTU202001802 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2020-07-27 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-2307202021062800.pdf 未授權公開取用 | 1.07 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。