全同態加密 (Fully Homomorphic Encryption, FHE) 允許直接對加密後的密文進行運算，可等同於對其未加密的明文進行相同的運算，從而保留雲端計算和數據隱私的雙重優勢。然而，全同態加密的安全性是建立在大量複雜的同態運算之上，因此在全同態加密成為普遍應用之前，許多人致力於降低同態運算的複雜度以及開發低複雜度的硬體加速器。本論文著重在低複雜度且可重組之非二次冪數論轉換 (Number Theoretic Transform, NTT) 架構設計，其主要應用於 BGV-FHE 方案中的多項式乘法運算，於同態乘法、密鑰交換 (key-switching)、模數交換 (modulus-switching) 以及重加密 (recryption) 等重要運算中皆會大量使用到多項式乘法運算。
本研究透過互質因子算法與雷德演算法遞迴拆解的優化方法可將大點數NTT透過分解成多個小點數運算來求得，進而得到較低的運算複雜度與記憶體需求量。以78881點NTT的應用為例，使用所提出之演算法所需的模乘法和模加法的數量相較於相關文獻之方法減少了約 3.13 和 2.75 倍。而在記憶體需求方面，隨機存取記憶體 (RAM) 與唯讀記憶體 (ROM)之需求量可分別減少到HElib所需之30%與0.047%。在硬體實現方面，採用所提出之可重組化運算元件 (Processing Element, PE)，其執行NTT運算所需的週期(cycle)數與採用以8為底數(radix-8) 蝴蝶單元之布魯斯坦快速傅立葉轉換(Bluestein's FFT)相仿，對於大點數NTT如77531與78881而言，其記憶體面積的改善程度更加顯著，可分別減少到HElib所需之57% 和 63%。

Fully homomorphic encryption (FHE) basically allows the typical operations to be performed directly on the encrypted data, thus it successfully retains the actual benefits of cloud computing and data privacy. However, the security level of FHE is eventually built on a huge amount of complex homomorphic operations. More efforts should be devoted in order to reduce the complexity of homomorphic evaluation algorithms and developing low-complexity hardware accelerator before the pervasive applications of FHE. This work mainly focuses on the low complexity and reconfigurable NTT defined over non-power-of-two cyclotomic polynomial rings, that can be applied in polynomial multiplication, key-switching, modulus switching and bootstrapping processes in the BGV-FHE scheme.
The resulting complexity is optimized by applying the prime-factor factorization scheme followed by the iterative decomposition method. For example, when the 78881-th cyclotomic polynomial is being considered, about 3.13 and 2.75 times of improvement will be found in the total number of required modular multiplication and modular addition. In terms of hardware implementation, by adopting the proposed architecture, it can keep the cycle less than or equal to Bluestein’s FFT using radix-8 butterfly unit but the total memory area can be gradually reduced to 57% and 63% when adopting the 77531-th and 78881-th cyclotomic polynomials, respectively.

[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] N. P. Smart and F. Vercauteren, “Fully homomorphic SIMD operations,” Designs, Codes Cryptogr., vol. 71, no. 1, pp. 57-81, 2014.
[5] ——, “HElib design principles,” Tech. Rep., 2020. [Online]. Available: https://homenc.github.io/HElib/documentation/Design Document/HElib-design.pdf
[6] S. Halevi and V. Shoup, “Bootstrapping for HElib,” in EUROCRYPT, pp. 641-670, 2015.
[7] 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, K. Nyberg, Ed. Springer Berlin Heidelberg, vol. 5086, pp. 54–72, 2008
[8] 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.
[9] H.J. Hsu and M.D. Shieh, “VLSI Architecture of Polynomial Multiplication for BGV Homomorphic Encryption,” International Symp. Circuits and Systems, May 2020
[10] I. J. Good, “The interaction algorithm and practical Fourier analysis,” J. Roy. Stat. Soc., ser. B, vol. 20, pp, 361 -372, 1958.
[11] C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, vol. 56, pp. 1107–1108, June 1968.
[12] C. TEMPERTON, Self-sorting mixed-radix Fast Fourier Transforms, J. Cotnpul. Phys. 52 (1983). 1-23.
[13] S. Winograd, “On computing the discrete Fourier transform,” Mathematics of Computation, vol. 2, no. 141, pp. 175–199, 1978.
[14] L.I. Bluestein, “A linear filering approach to the computation of the discrete Fourier transform,” in Northeast Electornics Research and Enginnering Meeting Rec., vol. 10, pp. 218-219, 1968.
[15] D. D. Chen, N. Mentens, F. Vercauteren, S. S. Roy, R. C. Cheung, D. Pao, and I. Verbauwhede, “High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 62, no. 1, pp. 157–166, 2014.
[16] S. Sinha Roy, F. Turan, K. Jarvinen, F. Vercauteren and I. Verbauwhede, "FPGA-Based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data," 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA), 2019, pp. 387-398.
[17] M. S. Riazi, K. Laine, B. Pelton, and W. Dai, “HEAX: An architecture for computing on encrypted data,” in Proc. 25th Int. Conf. Architectural Support Program. Lang. Operating Syst., 2020, pp. 1295–1309.
[18] D. P. Kolba and T. W. Parks, “A prime factor FFT algorithm using highspeed convolution,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 25, no. 3, pp. 281–294, 1977.
[19] C. Hsiao, Y. Chen and C. Lee, "A Generalized Mixed-Radix Algorithm for Memory-Based FFT Processors," in IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 57, no. 1, pp. 26-30, Jan. 2010.
[20] K. Xia, B. Wu, T. Xiong and T. Ye, "A Memory-Based FFT Processor Design With Generalized Efficient Conflict-Free Address Schemes," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 6, pp. 1919-1929, June 2017.
[21] S. Liu and D. Liu, "A High-Flexible Low-Latency Memory-Based FFT Processor for 4G, WLAN, and Future 5G," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 27, no. 3, pp. 511-523, March 2019
[22] J. Chen, J. Hu, S. Lee and G. E. Sobelman, "Hardware Efficient Mixed Radix-25/16/9 FFT for LTE Systems," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 2, pp. 221-229, Feb. 2015.
[23] X. Shih, H. Chou and Y. Liu, "VLSI Design and Implementation of Reconfigurable 46-Mode Combined-Radix-Based FFT Hardware Architecture for 3GPP-LTE Applications," in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 65, no. 1, pp. 118-129, Jan. 2018
[24] F. Qureshi, M. Garrido, and O. Gustafsson, “Unified architecture for 2, 3, 4, 5, and 7-point DFTs based on Winograd Fourier transform algorithm,” Electron. Lett., vol. 49, no. 5, pp. 348–349, May 2013.
[25] C. Gentry, S. Halevl, and N.P. Smart, “Homomorphic evaluation of the AES circuit,” in Proc. Advances in cryptology, ser. LNCS, 2012, pp. 850-867.
[26] 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.
[27] Y. Doröz, E. Öztürk and B. Sunar, "Accelerating Fully Homomorphic Encryption in Hardware," in IEEE Transactions on Computers, vol. 64, no. 6, pp. 1509-1521, 1 June 2015.
[28] J. Ye and M. Shieh, "Low-Complexity VLSI Design of Large Integer Multipliers for Fully Homomorphic Encryption," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 26, no. 9, pp. 1727-1736, Sept. 2018.
[29] P.N. Swarztrauber, R.A. Sweet, W.L. Briggs, V.E. Henson and J. Otto, “Bluestein's FFT for arbitrary N on the hypercube”, Parallel Computing 17, 1991, pp. 607-617.
[30] 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
[31] J. Fan and F. Vercauteren, “Somewhat practical fully homomorphic encryption,” in Proc. Advances in cryptology, ser. IACR Cryptology ePrint Archive, 2012.
[32] C. Gentry, A. Sahai, and B. Waters, ‘‘Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based,’’ in Proc. Annu. Cryptol. Conf. (CRYPTO), pp. 75–92, 2013.
[33] L. Ducas and D. Micciancio, “FHEW: Bootstrapping homomorphic encryption in less than a second,” in Proc. Annu. Int. Conf. Theory Appl. Cryptographic Techn., pp. 617–640, 2015.
[34] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, ‘‘TFHE: Fast fully homomorphic encryption over the torus,’’ J. Cryptol., vol. 33, no. 1, pp. 34–91, Jan. 2020.
[35] J. H. Cheon, A. Kim, M. Kim, and Y. S. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in Proc. Advances in Cryptology – ASIACRYPT 2017, Part I (Lecture Notes in Computer Science), 409–437, 2017.