近幾年，資安議題越來越被重視，甚至會改變整個產業鏈的生態。隨著科技的進步以及量子電腦的運算能力越來越強，能在多項式時間內就破解現行的加密系統。全同態加密(Fully Homomorphic Encryption)是一套能抵擋量子電腦攻擊的加密系統，並且允許資料在密文狀態進行運算。目前比較備受關注的全同態加密系統方案為帶錯誤的環學習(Ring learning with errors)方案，其運算在多項式環上，並透過雙重中國餘數定理運算來降低運算複雜度，雙重中國餘數定理運算是由整數中國餘數定理(Integer-CRT)再加上多項式中國餘數定理(Polynomial-CRT)組成。其中多項式中國餘數定理運算可視作為離散傅立葉轉換，但由於多項式的項數並非一定是二的冪次方，並不能直接使用庫利-圖基(Cooley-Tukey)演算法，而是採用布魯斯坦快速傅立葉轉換(Bluestein’s FFT)演算法，該演算法適用於任意點數的傅立葉轉換。
因此在本篇論文我們提出應用於全同態加密的布魯斯坦快速傅立葉轉換硬體編譯器，輸入全同態加密系統的參數，接著該編譯器就會產生符合於輸入參數的布魯斯坦快速傅立葉轉換的硬體，該硬體具有良好的效能，並且採用了混合基底單阜合併記憶體定址演算法(Mixed Radix Single-port Merged Bank Memory addressing algorithm)，該定址演算法也是我們在本篇論文所提出的，最後我們也提供了可配置的布魯斯坦快速傅立葉轉換硬體，可由同一硬體進行不同點數的傅立葉轉換。

In recent years, information security issues have been received more and more attention and will even change the ecology of the entire industrial chain. With the advancement of technology and the enhancement of quantum computer calculations, current encryption systems can be cracked in polynomial time. Fully Homomorphic Encryption is an encryption system that can resist quantum computer attacks and allows data to be calculated in the ciphertext. At present, a fully homomorphic encryption scheme that has attracted much attention is RLWE (Ring learning with errors) scheme, which calculates over a polynomial ring, and then we can use Double-CRT to reduce the computational complexity of polynomial calculations. Double-CRT computing is composed of the integer-CRT and the polynomial-CRT, which the polynomial-CRT can be seen as the DFT computation. However, the number of terms in a polynomial is not a power of two, so Cooley-Tukey algorithm cannot be used. But we can use Bluestein’s FFT algorithm, which is applicable to any number of points.
Therefore, in this paper, we propose the Bluestein’s FFT hardware compiler for fully homomorphic encryption. We input the fully homomorphic encryption parameters to the compiler, and then the compiler will generate the Bluestein’s FFT hardware according to the input parameters. The hardware generated by this compiler has good performance and adopts the mixed radix single-port merged bank memory addressing algorithm, which is also proposed by us in this paper. Finally, we also provide the configurable Bluestein’s FFT hardware, which can be configured to perform BFFT with any number of points.

[1] R. C. Agarwal and C. S. Burrus, “Number theoretic transforms to implement fast digital convolution,” in Proceedings of the IEEE, vol. 63, no. 4, pp. 550-560, April 1975.
[2] P. Barrett, “Communications authentication and security using public key encryption - A design for implementation,”. Master’s thesis, Oxford University, Sep 1984.
[3] L.I. Bluestein, “A linear filtering approach to the computing of the discrete Fourier transform,” Northeast Electronics Research and Engineering Meeting Record 10 ,1968
[4] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,”in Proc. IEEE 3rd Innovations in Theoretical Computer Science(ITCS),pp.309-325, 2012
[5] Z. Brakerski,” Fully homomorphic encryption without modulus switching form classical GapSVP ,” in Proc. Advances in cryptology, ser. LNCS, pp.868-886, 2012
[6] Z. Brakerski, and V. Vaikuntanathan,” Efficient fully homomorphic encryption from (standard) LWE,” in Proc. IEEE 52nd Annual Symp. On Foundations of Computer Science(FOCS), pp97-106, 2011
[7] Z. Brakerski, and V. Vaikuntanathan, “Fully homomorphic encryption from ring-LWE and Security for key dependent messages,” in Proc. Advances in cryptology, ser. LNCS, pp 505-524, 2011
[8] M.V. Dijk, C. Gentry, S. Halevl, and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” in Proc. Annu. Int. Conf. Theory Appl. Cryptograph. Techn, pp.24-43, 2010
[9] Y. Doroz, E. Ozturk, and B. Sunar, “Acceleration fully homomorphic encryption in hardware,” IEEE Trans. Comput., vol. 64, no.6, pp.1509-1521, Jun 2015
[10] C. Gentry, S. Halevl, and N.P. Smart, “Homomorphic Evaluation of the AES Circuit,” Springer, in Annual Cryptology Conference, pp 850-867, 2012
[11] C. Gentry, A. Sahai, and B.Waters, “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, ” in Proc. Advances in Cryptology , ser. LNCS, pp. 75 – 92 , 2013
[12] C. Gentry,”Implementing Gentry’s fully homomorphic encryption scheme, ” in Proc. Annu. Int. Conf. Theory Appl. Cryptograph., ser. LNCS, pp. 129-148, 2011
[13] C. Gentry,” Fully homomorphic encryption using ideal lattices,” In Proc. 41st Annu. ACM Symp. Theory Comput., pp. 169-178, 2009
[14] S. Halevi, and V. Shoup,” Bootstreapping for HElib,” in Proc. Advances in Cryptology, ser. LNCS, pp.641-670, 2015
[15] S. Halevi, and V. Shoup, “Algorithms in HElib”, in Proc. Annu. Int. Crypto.(CRYPTO). Santa Barbara, CA, USA: Springer-Verlag, pp.554-571, Aug ,2013
[16] J.N Ji, and M.D. Shieh,” Efficient comparison and Swap on Fully Homomorphic Encrypted Data,” IEEE International Symposium on Circuits and Systems. (ISCAS) ,2019.
[17] Y. Kong, "Optimizing the Improved Barrett Modular Multipliers for Public-Key Cryptography," 2010 International Conference on Computational Intelligence and Software Engineering, Wuhan, pp. 1-4, 2010.
[18] K. Lauter, M. Naehring, and V. Vaikuntanathan,” Can homomorphic encryption be practical?”, in Proc. 3rd ACM workshop on Cloud computing security workshop, pp. 113-124, 2011.
[19] H.F. Luo, Y.J. Liu, and M.D. Shieh,” Efficient memory addressing algorithms for FFT processor design”, IEEE Trans VLSI Syst., vol. 23, no. 10, pp. 2162-2172, Oct ,2015.
[20] R.L. Rivest, L. Adleman, and M.L. Dertouzos, “On the data banks and privacy homomorphisms,” in Foundations of secure computation, pp. 169-180, 1978
[21] 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, pp.607-617, 1991
[22] W. Wang, Y. Hu, L.Chen , X.Huang , and B. Sunar,”Exploring the feasibility of fully homomorphic encryption ,”IEEE Trans Comput. vol. 64, no. 3, pp. 698-706, Mar. 2015
[23] 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, pp. 1727-1736, 2018