全同態加密 (Fully Homomorphic Encryption, FHE) 在近幾年一直為廣受討論之領域，因為其可以在不解密的情況下直接對密文進行所需的操作，進而確保資料之安全性及隱私權。然而全同態加密目前未能成為普遍應用之原因為其運算複雜度及資料存儲量非常大，目前許多現有文獻也都在探討解決這些問題。本論文著重於透過硬體加速的方法降低其運算複雜度，主要具體貢獻可分為兩點。其一為設計可應用於現今BGV-FHE參數下之非二次冪布魯斯坦數論轉換 (Bluestein’s Number Theoretic Transform, BNTT)。其二為由於密鑰交換 (key switching) 為全同態加密中最複雜之演算法之一，因此基於所提出之BNTT提出有效率之密鑰交換架構，進而降低全同態加密整體系統之複雜度。
本研究透過選擇特殊低漢明權重之質數，以優化貝雷模乘法器 (Barrett Modular Multiplier) 的設計並減少隨機存取記憶體 (SRAM) 及唯讀記憶體 (ROM)。在點數為21845的例子下，與現有文獻相比，所提出之架構在單個BNTT中實現了約13%的面積改善。在密鑰交換方面，本研究根據BGV-FHE之參數提出可應用於彈性參數選擇之密鑰交換架構，並透過全平行之架構以及流水線之運算單元設計，在大點數時顯著降低緩衝記憶體之使用。此外根據輸入之吞吐量，摺疊所需之BNTT及BINTT模組數，得到最有面積優勢之密鑰交換架構。與現有文獻相比，所提出之架構在大部分參數下具有優勢，在大點數優勢尤為顯著，整體效能最高可提升39.15%。

Fully Homomorphic Encryption (FHE) has been a widely discussed field in recent years due to its ability to perform desired operations on ciphertext without decryption, thereby ensuring data security and privacy. However, the widespread application of FHE is hindered by its computational complexity and large memory requirements. Many existing studies have focused on addressing these challenges. This work focuses on reducing the computational complexity of FHE through hardware acceleration, making two main contributions. Firstly, a design is proposed for the Bluestein's Number Theoretic Transform (BNTT), which is applicable to the current BGV-FHE parameters. Secondly, due to key switching is one of the most complex algorithms in fully homomorphic encryption, a highly efficient key switching architecture based on the proposed BNTT is presented to reduce the overall complexity of FHE systems.
This work focuses on optimizing the design of the Barrett Modular Multiplier and reducing the usage of memory through the special selection of prime numbers with low Hamming weight. In the case of point size 21845, the proposed architecture achieves approximately 13% area improvement compared to existing literature in a single BNTT implementation. For key switching, a key switching architecture suitable for flexible parameter selection based on BGV-FHE parameters is proposed. Through a fully parallel architecture with pipelined computation units design, the usage of buffer memory is significantly reduced for large point sizes. Additionally, by folding the required number of BNTT and BINTT modules based on the input throughput, an optimized key switching architecture with superior area efficiency is obtained. Compared to existing literature, the proposed architecture exhibits advantages in most parameter settings, with particularly significant benefits for large point sizes, achieving up to 39.15% overall performance improvement.

[1] R. L. Rivest, L. Adleman, and M. L. Dertouzos, “On the banks and privacy homomorphisms,” in Foundations of secure computation, 1978, pp. 169-180.
[2] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proc. 41st Annu. ACM STOC, pp. 169-178, 2009.
[3] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” in Proc. 3rd Innovations in Theoretical computer Science Conf., pp. 309-325, 2012.
[4] Z. Brakerski and V. Vaikuntanathan, ‘‘Efficient fully homomorphic encryption from (standard) LWE,’’ SIAM Journal on Computing, vol. 43, no. 2, pp. 831–871, Jan. 2014.
[5] Z. Brakerski and V. Vaikuntanathan, ‘‘Fully homomorphic encryption from ring-LWE and security for key dependent messages,’’ in Proc. 31st Annu. Cryptol. Conf. Adv. Cryptol. (CRYPTO), Santa Barbara, CA, USA, Aug. 2011, pp. 505–524.
[6] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, “TFHE: fast fully homomorphic encryption over the torus,” IACR Cryptol. ePrint Arch., 2018.
[7] N. Gama, M. Izabachène, P. Q. Nguyen, and X. Xie, “Structural lattice reduction: Generalized worst-case to average-case reductions and homomorphic cryptosystems,” in Advances in Cryptology—EUROCRYPT 2016. Cham, Switzerland: Springer, 2016, pp. 528–558.
[8] J. H. Cheon, A. Kim, M. Kim, and Y. Song, ‘‘Homomorphic encryption for arithmetic of approximate numbers,’’ in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur., Hong Kong, 2017, pp. 409–437.
[9] P. Longa and M. Naehrig, “Speeding up the number theoretic transform for faster ideal lattice-based cryptography,” in Cryptology and Network Security. Milan, Italy: Springer, Nov. 2016, pp. 124–139.
[10] Duong-Ngoc P., Kwon S., Yoo D., Lee H. “Area-efficient number-theoretical transform architecture for Homomorphic encryption.” in IEEE Trans. Circuits Syst. I Regul. Pap. 2023, 70, 1270–1283.
[11] C.C. Huang, J.N. Ji and M.D. Shieh, “On Compare-and-Swap Optimization for Fully Homomorphic Encrypted Data,” in Proc. Int. Symp. Circuits and Systems,, May 2021.
[12] P. A. Milder, F. Franchetti, J. C. Hoe, and M. Puschel, "Hardware implementation of the discrete fourier transform with non-power-of-two problem size," in Proc. IEEE Int. Conf. Acoustics Speech and Signal Processing, pp. 1546-1549, 2010.
[13] L. I. Bluestein, “A linear filtering approach to the computation of the discrete Fourier transform,” in Northeast Electronics Research and Engineering Meeting Rec., vol. 10, 1968, pp. 218–219.
[14] C. Van Loan, “Computational Frameworks for the Fast Fourier Transform,” SIAM, 1992.
[15] S. Halevi and V. Shoup, “HElib,” 2013.
[16] S.Y. Wu, K.Y. Chen and M.D. Shieh, “Efficient VLSI architecture of Bluestein’s FFT for fully homomorphic encryption,” in Proc. Int. Symp. Circuits and Systems, May 2022.
[17] H.J. Hsu and M.D. Shieh, “VLSI architecture of polynomial multiplication for BGV homomorphic encryption,” in Proc. Int. Symp. Circuits and Systems, May 2020.
[18] J. A. Solinas, “Generalized Mersenne numbers,” Univ. Waterloo, Waterloo, ON, Canada, Tech. Rep. CORR 99-39, 1999.
[19] M Sadegh Riazi, Kim Laine, Blake Pelton, and Wei Dai. “HEAX: An architecture for computing on encrypted data.” in Proceedings of the 25th international conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XXV), 2020.
[20] J. Angel and G. Morales-Luna, “Solinas primes of small weight for fixed sizes,” IACR Cryptol, ePrint Arch, 2010.
[21] P. Barrett, “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor,” in Advances in Cryptology – CRYPTO ’86: Proceedings, 1987.
[22] S. Kim, K. Lee, W. Cho, J. H. Cheon, and R. A. Rutenbar, “FPGA-based accelerators of fully pipelined modular multipliers for homomorphic encryption,” in Proc. ReConFig, 2019.