全同態加密（Fully Homomorphic Encryption, FHE）是一種保障資料安全性和數據隱私性的雲端計算技術。其核心概念是在不對資料解密的情況下，直接對密文進行加、減、乘等同態運算，效果等同於對未加密的明文進行相同運算。然而，同態運算為了保障計算資料的安全性，會增加一定程度的運算複雜度。目前學者致力於簡化全同態運算的演算法複雜度，並開發低複雜度的硬體加速器，降低使用全同態加密技術所需的成本。本論文的重點是開發適用於二次冪下混合基底參數之反轉換負循環摺積（Inverse Negative Wrapped Convolution, INWC）硬體設計，並針對低面積和低複雜度需求進行優化。該硬體設計主要應用於多項式乘法運算，但也廣泛用於密鑰交換（key-switching）等重要的同態運算中。
通過引入負循環摺積算法和循環因子產生器的優化方法，本研究成功避免了傳統二次冪數論轉換中的零填充和模多項式運算，同時減少了循環因子的儲存量。以65536點的INWC應用為例，循環因子的儲存量從65536筆壓縮至僅1296筆，壓縮率達97.9%。這節省了儲存空間並提升了計算效率。此外，該研究進一步將NWC的前處理、INWC的後處理和縮放因子過程合併到快速傅立葉轉換（FFT）的演算法中，分別對NWC和INWC減少了N次和2N次的模乘法運算數量。實驗結果顯示，本研究的架構設計在計算效率和面積消耗方面明顯優於其他文獻的結果。

Fully Homomorphic Encryption (FHE) is a cloud computing technology that ensures data security and privacy. Its core concept is to perform homomorphic operations such as addition, subtraction, and multiplication directly on encrypted ciphertext without decrypting the data, achieving the same results as performing the operations on unencrypted plaintext. However, homomorphic operations increase the computational complexity to ensure the security of the computed data. Currently, researchers are focused on simplifying the algorithmic complexity of FHE and developing low-complexity hardware accelerators to reduce the cost of using FHE techniques. The main focus of this paper is the development of a hardware design for Inverse Negative Wrapped Convolution (INWC) tailored for mixed-base parameters in powers of two. The design is optimized for area-efficiency and low complexity requirements. While the hardware design is primarily applied to polynomial multiplication operations, it is also widely used in essential homomorphic operations such as key-switching.
By introducing optimized methods for Negative Wrapped Convolution (NWC) algorithm and twiddle factor generator, this study successfully eliminates zero-padding and modular polynomial operations in NTT (Number Theoretic Transform), while reducing the storage requirement for twiddle factors. Taking the example of a 65536-point INWC application, the storage requirement for twiddle factors is compressed from 65536 to only 1296, achieving a compression rate of 97.9%. This saves storage space and improves computational efficiency. Furthermore, this study further integrates the pre-processing for NWC, the post-processing and the scaling factor process for INWC into the FFT algorithm, reducing the number of modular multiplications by N times and 2N times required for NWC and INWC, respectively. Experimental results demonstrate that the architectural design in this work significantly outperforms the results of previous works in terms of computational efficiency and area consumption.

[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] “HElib design principles,” Tech. Rep., 2020. [Online]. Available
[5] L.I. Bluestein, “A linear filering approach to the computation of the discrete Fourier transform,” in Northeast Electornics Research and Enginnering Meeting Rec, 1968.
[6] H.J. Hsu and M.D. Shieh, “VLSI Architecture of Polynomial Multiplication for BGV Homomorphic Encryption,” in International Symp. Circuits and Systems. 2020
[7] J. Cooley and J. Turkey, “An algorithm for the machine computation of complex Fourier series,” Mathematics of Computation, vol. 19, no. 90, pp. 297–301, 1965.
[8] Gentleman, W.M., Sande, G.: “Fast Fourier Transforms: for fun and profit,” In: American Federation of Information Processing Societies: Proceedings of the AFIPS '66 Fall Joint Computer Conference, 1966
[9] V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen, “SWIFFT: A modest proposal for FFT hashing,” in Fast Software Encryption, ser. Lecture Notes in Computer Science, vol. 5086, pp. 54–72, 2008.
[10] Sujoy Sinha Roy, Frederik Vercauteren, Nele Mentens, Donald Donglong Chen, and Ingrid Verbauwhede. “Compact ring-LWE crypto-processor,” In CHES’14, 2014.
[11] Patrick Longa and Michael Naehrig. “Speeding up the number theoretic transform for faster ideal lattice-based cryptography,” Cryptology ePrint Archive, 2016.
[12] Thomas Poppelmann, Tobias Oder, and Tim Gijneysu. “High-performance ideal lattice-based cryptography on 8-bit ATxmega microcontrollers,” Cryptology ePrint Archive, 2015.
[13] Sujoy Sinha Roy, Furkan Turan, Kimmo Järvinen, Frederik Vercauteren, and Ingrid Verbauwhede. “FPGA-Based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data,” In HPCA. 2019.
[14] F. Turan, S. Roy, and I. Verbauwhede, “HEAWS: An Accelerator for Homomorphic Encryption on the Amazon AWS FPGA,” IEEE Transactions on Computers, 2020.
[15] N. Zhang, B. Yang, C. Chen, S. Yin, S. Wei, and L. Liu, “Highly efficient architecture of NewHope-NIST on FPGA using low-complexity NTT/INTT,” IACR Trans. Cryptograph. Hardw. Embedded Syst., vol. 2020, no. 2, pp. 49–72. 2020.
[16] Junfeng Fan and Frederik Vercauteren. 2012a. “Somewhat practical fully homomorphic encryption,” IACR Cryptology ePrint Archive 2012.
[17] James W. Cooley and John W. Tukey. “An algorithm for the machine calculation of complex fourier series,” Mathematics of Computation, 19(90):297–301. 1965.
[18] Gentleman, W.M., Sande, G, “Fast fourier transforms for fun and prot,” In: American Federation of Information Processing Societies: Proceedings of the AFIPS '66 Fall Joint Computer Conference, November 7-10, 1966.
[19] F. Winkler. “Polynomial Algorithms in Computer Algebra,” 1996
[20] H.-F. Luo, Y.-J. Liu, and M.-D. Shieh, “Efficient memory-addressing algorithms for FFT processor design,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2015.
[21] Y. Kong, “Optimizing the Improved Barrett Modular Multipliers for Public-Key Cryptography,” 2010 International Conference on Computational Intelligence and Software Engineering, 2010, pp. 1-4
[22] Z. Li, J. Ren, G. Du, Z. Tu, X. Wang, Y. Yin, and Y. Ouyang, “An area-efficient large integer NTT-multiplier using discrete twiddle factor approach,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 70, no. 2, pp. 751–755. 2023
[23] F. Yaman, A. C. Mert, E. Ozturk, and E. Savas, “A hardware accelerator for polynomial multiplication operation of CRYSTALS-KYBER PQC scheme,” in Proc. Design, Autom. Test Eur. Conf. Exhib, pp. 1020–1025.
[24] W. Wang, X. Huang, N. Emmart, and C. Weems, “Vlsi design of a large-number multiplier for fully homomorphic encryption,” IEEE Transactions on Very Large-Scale Integration (VLSI) Systems, vol. 22, no. 9, pp. 1879–1887, 2013.
[25] J.-H. Ye and M.-D. Shieh, “Low-complexity vlsi design of large integer multipliers for fully homomorphic encryption,” IEEE Transactions on Very Large-Scale Integration (VLSI) Systems, vol. 26, no. 9, pp. 1727–1736, 2018.
[26] X. Feng and S. Li, “Accelerating an fhe integer multiplier using negative wrapped convolution and ping-pong fft,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 66, no. 1, pp. 121–125, 2019.
[27] Robin Geelen, Michiel Van Beirendonck, Hilder V. L. Pereira, Brian Huffman, Tynan McAuley, Ben Selfridge, Daniel Wagner, Georgios Dimou, Ingrid Verbauwhede, Frederik Vercauteren, David W. Archer, “BASALISC: Programmable Asynchronous Hardware Accelerator for BGV Fully Homomorphic Encryption,” Cryptology ePrint Archive, 2
[28] P. Duong-Ngoc, S. Kwon, D. Yoo, and H. Lee, “Area-efficient number theoretic transform architecture for homomorphic encryption,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 70, no. 3, pp. 1270–1283. 2023
[29] G. Xin, Y. Zhao, and J. Han, “A multi-layer parallel hardware architecture for homomorphic computation in machine learning,” in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS), pp. 1–5.
[30] S. Kim, K. Lee, W. Cho, Y. Nam, J. H. Cheon, and R. A. Rutenbar, “Hardware architecture of a number theoretic transform for a bootstrappable RNS-based homomorphic encryption scheme,” in Proc. IEEE 28th Ann. Int. Symp. 2020
[31] 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
[32] Joan Daemen and Vincent Rijmen. Nov. 2001. “Advanced Encryption Standard (AES),” National Institute of Standards and Technology (NIST),
[33] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the Acm, 1978.
[34] V. Miller, ‘‘Use of elliptic curves in cryptography,’’ in Advances in Cryptology–(CRYPTO) (Lecture Notes in Computer Science), 1986, pp. 417–426.