全同態加密 (Fully Homomorphic Encryption, FHE) 可以直接對密文進行運算，等效於對其未加密的明文元素進行相同的運算，而不用對密文執行解密程序，可確保資料的安全與隱密性，因此目前被廣泛地關注與討論。BGV全同態加密方案是目前討論較熱烈，且可配合使用聚合明文技術來大幅提高明文的使用率；結合重加密技術，可使其應用的範圍不再受限制。BGV全同態加密的數學運算定義在多項式環，本論文探索針對使用分圓多項式環的聚合明文，以及重加密的應用之多項式乘法的硬體架構。並展示如何有效地結合分圓多項式、互質因子算法以及雷德演算法的特性，以得出基於中國餘數定理 (CRT) 的新穎架構設計想法。實驗結果顯示，在足夠安全性下的參數考量下與現有的技術相比，本論文所提出的解決方案可以顯著地提高運算的效率，並且大幅降低運算過程中所需的記憶體空間。舉例而言，當使用參數為21845次分圓多項式時，與Chen所提出的架構在足夠安全的條件之下相比，可以將一次多項式乘法所需的模加法與模乘法的運算量分別減少3.11倍與13.02倍，並且是在僅使用32個明文槽且皆僅加密一位元的情況下比較。如果是在所有的明文槽皆可使用的情況下相比，本論文所提出架構設計的效能改進是非常可觀的。若與HElib的實現方式相比，假設參數為21845次分圓多項式，本論文提升使用基數為4與8的蝴蝶形單元所實現的快速傅立葉轉換架構運算速度分別約提升2.85倍以及1.56倍，並且隨機存取記憶體 (RAM) 的記憶空間需求量減少為HElib所需的33%，唯讀記憶體 (ROM) 的記憶空間需求量大幅減少至HElib的0.42%。

Fully homomorphic encryption (FHE) has attracted a lot of attention because computations can be directly performed on ciphertexts. This work explores the hardware architecture of polynomial multiplication defined in BGV-FHE, targeting the applications of aggregate plaintext using cyclotomic polynomials. We show how to effectively combine the characteristics of cyclotomic polynomials, the prime-factor FFT algorithm and the Rader’s FFT algorithm to obtain a novel design derived by the concept of Chinese Remainder Theorem. Experimental results show that a significant improvement in terms of operation reduction and memory requirements can be achieved by adopting the proposed schemes as compared to existing works assuming a comparable security level. For example, about 3.11 and 13.02 times improvement in the total number of required modular addition and multiplication, respectively, can be obtained by using 32 one-bit aggregate slots as compared to Chen’s work when the 21845-th cyclotomic polynomial is considered. The improvement could be huge if all of the available slots are involved in applications. Compared with the results using HElib, the proposed architecture obtains about 2.85 times and 1.56 times speedup by using radix-4 and radix-8 butterfly units in FFT design, respectively. In addition, the required RAM and ROM size are reduced to 33% and 0.42%, respectively, when adopting the 21845-th cyclotomic polynomial.

[1] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proc. 41st Annu. ACM STOC, pp. 169-178, 2009.
[2] C. Gentry, S. Halevi, and N. Smart, “Homomorphic evaluation of the AES circuit,” in Proc. CRYPTO, 2012.
[3] S. Halevi and V. Shoup, “Bootstrapping for HElib,” in EUROCRYPT, pp. 641-670, 2015.
[4] S. Halevi and V. Shoup, “Faster homomorphic linear transformations in HElib,” Cryptol. ePrint Arch., Tech. Rep. 2018/244, 2018.
[5] M. Naehrig, K. Lauter, and V. Vaikuntanathan, “Can homomorphic encryption be practical?,” in Proceedings of the 3rd ACM workshop on Cloud computing security workshop, pp. 113-124, ACM, 2011.
[6] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti, “A survey on homomorphic encryption schemes: Theory and implementation,” ACM Comput. Surveys., vol. 51, no. 4, p. 79, 2018.
[7] J.-N. Ji and M.-D. Shieh, “Efficient Comparison and Swap on Fully Homomorphic Encrypted Data,” in Proc. IEEE Internation Symposium on Circuits and Systems, pp. 1-4, May. 2019.
[8] D. D. Chen et al.,“High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 62, no. 1, pp. 157-166, Jan. 2015.
[9] 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.
[10] N. P. Smart and F. Vercauteren, “Fully homomorphic SIMD operations,” Designs, Codes Cryptogr., vol. 71, no. 1, pp. 57-81, 2014.
[11] S. Halevi and V. Shoup, “HElib,” 2013.
[12] 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.
[13] I. J. Good, “The interaction algorithm and practical Fourier analysis,” J. Roy. Stat. Soc., ser. B, vol. 20, pp, 361 -372, 1958.
[14] C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, vol. 56, pp. 1107–1108, June 1968.
[15] C. Genrty, S. Halevi, and N. P. Smart, “Fully homomorphic encryption with polylog overhead,” in EUROCRYPT, 2012.
[16] J. M. Pollard, “The fast Fourier transform in a finite field,” Math.Comput., vol. 25, pp. 365–374, 1971.
[17] Y.-N. Chang and K. K. Parhi, “An Efficient Pipelined FFT Architecture,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 50, no. 6, pp. 322-325, June 2003.
[18] H. L. Groginsky and G. A. Works, “A Pipeline Fast Fourier Transform,” IEEE Trans. Comput., vol. c-19, no. 11, pp. 1015-1019, Nov. 1970.
[19] E. E. Swartzlander, W. K. W. Young, and S. J. Joseph, “A Radix 4 Delay Commutator for Fast Fourier Transform Processor Implementation,” IEEE J. Solid-State Circuits, vol. sc-19, no. 5, pp. 702-709, Oct. 1984.
[20] C.-K. Chang, C.-P. Hung, and S.-G. Chen, “An efficient memory-based FFT architecture,” in Proc. IEEE Int. Symp. Circuits Syst., vol. 2. pp. 129-132, May. 2003.
[21] L. G. Johnson, “Conflict Free Memory Addressing for Dedicated FFT Hardware,” IEEE Trans. Circuits Syst. II, Analog Digit. Signal Process., vol. 39, no. 5, pp. 312-316, May. 1992.
[22] 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., vol. 23, no. 10, pp. 2162-2172, Oct. 2015.