数据加载中.....
|
请使用永久网址来引用或连结此文件:
https://nccur.lib.nccu.edu.tw/handle/140.119/158480
|
| 题名: | 基於 NTRU 全同態加密實現密文狀態下之反矩陣運算
Inverse Matrix Computation over Ciphertexts Based on NTRU Fully Homomorphic Encryption |
| 作者: | 林品翰
Lin, Pin-Han |
| 贡献者: | 左瑞麟
Tso, Ray-Lin
林品翰
Lin, Pin-Han |
| 关键词: | 後量子密碼學
全同態加密
同態電路邏輯閘
牛頓近似演算法
隱私保護運算
同態運算情境設計與應用
Post-Quantum Cryptography
Fully Homomorphic Encryption
Homomorphic Logic Gates
Newton’s Iteration Method
Privacy-Preserving Computation
Homomorphic Computing Scenarios and Applications |
| 日期: | 2025 |
| 上传时间: | 2025-08-04 13:58:42 (UTC+8) |
| 摘要: | 本研究旨在探索基於後量子密碼學（Post-Quantum Cryptography, PQC）的全同態加密（Fully Homomorphic Encryption, FHE）技術，將其應用於第三方運算場景，以實現安全的數據隱私保護。針對量子計算對傳統加密技術（如RSA 和 ECC）的威脅，本研究選用基於學習誤差問題（Learning with Errors, LWE）與 NTRU 的現有加密架構，並進一步設計與實作基於同態電路邏輯閘的運算方法，特別是全同態基本運算電路的設計。其中一項關鍵方法為將原本求取矩陣反元素的非線性問題，透過牛頓近似法（Newton’s Iteration）轉化為線性迭代問題，使之更適用於同態電路邏輯架構的實作。透過公式推導與數學論證，證明該方法在同態加密環境下具備可行性與後量子安全性，可於第三方運算中保障資料始終保持加密狀態，避免隱私洩露。本研究重點聚焦於設計適配全同態加密架構的電路邏輯閘運算演算法，並整合牛頓近似反矩陣求解機制，以支援對加密數據的有效操作。實驗評估部分，在第三方伺服器運算場景下，對加密資料處理效率與隱私保護能力進行全面測試，結果顯示所提出方法不僅能兼顧安全與效能，亦具實用性。最終，本研究在雲端計算（Cloud Computing）與多方安全計算（Secure Multi-Party Computation, MPC）等高隱私需求應用中，展現了良好的可行性與應用價值，後續將逐步分析其運算效率與誤差表現。
This study explores the application of Fully Homomorphic Encryption (FHE) based on Post-Quantum Cryptography (PQC) in third-party computation scenarios to ensure secure data privacy. In response to the threats posed by quantum computing to traditional cryptographic schemes such as RSA and ECC, this research adopts encryption frameworks based on Learning with Errors (LWE) and NTRU. It further designs and implements computation methods based on homomorphic circuit logic gates, focusing particularly on the construction of fundamental homomorphic arithmetic circuits. A key approach involves transforming the inherently nonlinear problem of matrix inversion into a linear iterative problem via Newton’s Iteration Method, making it more compatible with homomorphic circuit architectures. Through formal derivation and mathematical analysis, the feasibility and post-quantum security of this method are demonstrated within homomorphic encryption environments, ensuring that data remains encrypted throughout the computation process, thereby preventing privacy leakage. This research emphasizes the design of logic gate-based algorithms tailored to FHE frameworks and integrates Newton-based matrix inversion mechanisms to support effective operations on encrypted data. The experimental evaluation assesses both processing efficiency and privacy protection in third-party server scenarios. Results indicate that the proposed approach achieves a balance between security and performance, demonstrating practical applicability. Ultimately, this study presents strong feasibility and application potential in privacy-sensitive domains such as cloud computing and secure multi-party computation (MPC), with future work focusing on performance analysis and error behavior under FHE settings. |
| 參考文獻: | [1] C. Bonte, I. Iliashenko, J. Park, H. V. L. Pereira, and N. P. Smart, "FINAL: Faster FHE instantiated with NTRU and LWE," in *ASIACRYPT 2022*, published by the IACR, 2022.
[2] C. Gentry, A. Sahai, and B. Waters, "Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based," in *CRYPTO 2013*, 2013.
[3] C. Cheon, K. Han, S. Hong, J. Kim, and Y. Song, "Homomorphic Encryption for Arithmetic of Approximate Numbers," in ASIACRYPT 2017, Advances in Cryptology, pp. 409–437, Springer, 2017.
[4] X. Qin, R. Huang, and H. Fan, "An Effective NTRU-Based Fully Homomorphic Encryption Scheme," in Mathematical Problems in Engineering, Hindawi, vol. 2021, Article ID 6614578, 2021.
[5] K. Cong, D. Das, J. Park, and H. V. L. Pereira, "SortingHat: Efficient Private Decision Tree Evaluation via Homomorphic Encryption and Transciphering," in 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS 2022), 2022.
[6] Y. Huang and G. Duan, "A Privacy-Preserving Decision Tree Evaluation Scheme for Multiple Wearable Devices," in 2024 27th International Conference on Computer Supported Cooperative Work in Design (CSCWD), IEEE, 2024.
[7] L. T. Phong, Y. Aono, T. Hayashi, L. Wang, and S. Moriai, "PrivacyPreserving Deep Learning via Additively Homomorphic Encryption," in IEEE Transactions on Information Forensics and Security, vol. 13, no. 5, pp. 1333–1345, May 2018.
[8] K. Men, H. Li, B. Wang, and M. Liu, "An NTRU-based Homomorphic Encrypted Data Analysis System," in IEEEInternational Conference on Intelligent and Big Data Analytics(ICIBA), 2023.
[9] D.-T. Dam, T.-H. Tran, V.-P. Hoang, C.-K. Pham, and T.-T. Hoang,"A Survey of Post-Quantum Cryptography: Start of a New Race," in Cryptography, published by MDPI, 2023.
[10]R. J. McEliece, "A Public-Key Cryptosystem Based on Algebraic Coding Theory," in DSN Progress Report, published by JPL, 1978.
[11]J. Hoffstein, J. Pipher, and J. H. Silverman, "NTRU: A new high 42 speed public key cryptosystem," in Algorithmic Number Theory (ANTS III), LNCS 1423, published by Springer, 1998.
[12]O. Regev, "On lattices, learning with errors, random linear codes, and cryptography," in STOC 2005, published by ACM, 2005.
[13]J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. Schanck, P. Schwabe, B. Seiler, and D. Stebila, "CRYSTALS-Kyber: A CCAsecure module-lattice-based KEM," in EuroS&P 2018, published by IEEE, 2018.
[14]C. Peikert, "A Decade of Lattice Cryptography," in Foundations and Trends in Theoretical Computer Science, published by Now Publishers, 2016.
[15]Z. Brakerski and V. Vaikuntanathan, "Efficient fully homomorphic encryption from (standard) LWE," in FOCS 2011, published by IEEE, 2011.
[16]Z. Brakerski, "Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP," in CRYPTO 2012, LNCS 7417, published by Springer, 2012.
[17]A. López-Alt, E. Tromer, and V. Vaikuntanathan, "On-the-Fly Multiparty Computation on the Cloud via Multi-key FHE," in STOC 2012, published by ACM, 2012.
[18]J. Alperin-Sheriff and C. Peikert, "Faster bootstrapping with polynomial error," in CRYPTO 2014, LNCS 8616, published by Springer, 2014.
[19]L. Ducas and D. Micciancio, "FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second," in EUROCRYPT 2015, LNCS 9056, published by Springer, 2015.
[20]I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, "Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds," in ASIACRYPT 2016, LNCS 10031, published by Springer, 2016.
[21]J. H. Cheon, A. Kim, M. Kim, and Y. Song, "Homomorphic Encryption for Arithmetic of Approximate Numbers," in ASIACRYPT 2017, LNCS 10624, published by Springer, 2017.
[22]C. Gentry, S. Halevi, and N. P. Smart, "Homomorphic Evaluation of the AES Circuit," in CRYPTO 2012, LNCS 7417, published by Springer, 2012.
[23]C. Gentry, A. Sahai, and B. Waters, "Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based," in CRYPTO 2013, LNCS 8042, published by Springer, 2013.
[24]M. Yu, S. Carpov, A. Tempia-Calvino, and G. De Micheli, "On the Synthesis of High-Performance Homomorphic Boolean Circuits," in ICCAD 2023, published by IEEE, 2023.
[25]Z. Guan, R. Mao, Q. Zhang, Z. Zhang, Z. Zhao, and S. Bian, "AutoHoG: Automating Homomorphic Gate Design for Large-Scale Logic Circuit Evaluation," in IEEE Transactions on Computer-AidedDesign of Integrated Circuits and Systems, published by IEEE, 2024.
[26]J. Moon, Z. Omarov, D. Yoo, Y. An, and H. Chung, "Adaptive Successive Over-Relaxation Method for a Faster Iterative Approximation of Homomorphic Operations," in Cryptology ePrint Archive, Report 2024/1366, 2024.
[27]C. Bonte and F. Vercauteren, "Privacy-Preserving Logistic Regression Training," in BMC Medical Genomics, published by BioMed Central, 2018.
[28]M. Kim, Y. Song, S. Wang, Y. Xia, and X. Jiang, "Secure Logistic Regression Based on Homomorphic Encryption: Design and Evaluation," in JMIR Medical Informatics, published by JMIR, 2018.
[29]C. Hong, "Recent advances of privacy-preserving machine learning based on (Fully) Homomorphic Encryption," in Security and Safety, published by EDP Sciences, 2025.
[30]R. Bost, R. A. Popa, S. Tu, and S. Goldwasser, "Machine Learning Classification over Encrypted Data," in NDSS 2015, Internet Society, 2015.
[31]Á. Kiss, M. Naderpour, J. Liu, N. Asokan, and T. Schneider, "SoK: Modular and Efficient Private Decision Tree Evaluation," in PoPETs 2019, 2019.
[32]R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, "CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy" in ICML 2016, published by JMLR, 2016.
[33]J. J. Sim, F. M. Chan, S. Chen, B. H. M. Tan, and K. M. M. Aung, "Achieving GWAS with Homomorphic Encryption," in BMC Medical Genomics, published by BioMed Central, 2020.
[34]M. Wang, W. Zhao, K. Cheng, Z. Wu, and J. Liu, "Homomorphic Encryption Based Privacy Preservation Scheme for DBSCAN Clustering," in Electronics, published by MDPI, 2022.
[35]K Xu, BHM Tan, LP Wang, KMM Aung, and H Wang, "PrivacyPreserving Outsourcing Decision Tree Evaluation from Homomorphic Encryption," in Journal of Information Security and Applications, published by Elsevier, 2023.
[36]C. Wang, A. Wang, J. Xu, Q. Wang, and F. Zhou, "Outsourced Privacy-Preserving Decision Tree Classification Service over Encrypted Data," in Journal of Information Security and Applications, published by Elsevier, 2020.
[37]C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan, "GAZELLE: A Low Latency Framework for Secure Neural Network Inference," in USENIX Security 2018, USENIX Association, 2018.
[38]R. Dathathri, O. Saarikivi, H. Chen, K. Laine, K. Lauter, S. Maleki, M. Musuvathi, T. Mytkowicz, and K. V. Rajan, “CHET: an optimizing compiler for fully-homomorphic neural-network inferencing,” in PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 142–156, ACM, 2019.J. Fan and F. Vercauteren, "Somewhat Practical Fully Homomorphic Encryption," in Cryptology ePrint Archive, Report 2012/144, 2012.
[39]Y. Gong, X. Chang, J. Mišić, V. B. Mišić, J. Wang, and H. Zhu, "Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methods," in Cybersecurity, published by Springer, 2024.
[40]S. Halevi and V. Shoup, "Bootstrapping for HElib," in Journal of Cryptology, published by Springer, 2021.
[41]T. Lepoint and M. Naehrig, "A Comparison of the Homomorphic Encryption Schemes FV and YASHE," in Cryptology ePrint Archive, Report 2014/062, 2014. |
| 描述: | 碩士
國立政治大學
資訊科學系
112753132 |
| 資料來源: | http://thesis.lib.nccu.edu.tw/record/#G0112753132 |
| 数据类型: | thesis |
| 显示于类别: | [資訊科學系] 學位論文
|
文件中的档案:
| 档案 |
描述 |
大小 | 格式 | 浏览次数 |
|---|
| 313201.pdf | | 1422Kb | Adobe PDF | 0 | 检视/开启 |
|
在政大典藏中所有的数据项都受到原著作权保护.
|
