由於透過雲端運算(Cloud Computing)在網路上存取或運算資料愈趨普遍，安全性的問題也伴隨著產生。全同態加密(Fully Homomorphic Encryption)演算法可讓雲端伺服器直接對密文進行運算，以維持資料的隱私性。然而，此演算法目前仍需龐大的計算來確保安全性，其運算元長度可達百萬位元以上，造成整體系統運算效率受到限制。區塊式(Block-based)快速傅立葉轉換(Fast Fourier Transform)乘法演算法可實現大整數乘法運算，但隨著所劃分的區塊數目增加，乘法和加法的運算次數會相應增加，導致整體運算複雜度也會跟著提升，如何開發出有效率的大整數乘法演算法是一個重要課題。
本論文所提出的區塊式快速傅立葉轉換乘法演算法，主要是針對奇偶區塊的輸入資料設計不同的排列方式，並藉由奇偶區塊的快速傅立葉轉換結果的結合，取得結合區塊的快速傅立葉轉換結果，將這三類區塊的快速傅立葉反轉換結果經由累加和進位計算可得到大整數乘法結果。此外，透過改變區塊間的執行順序，可進一步降低累加計算所需的儲存空間。相較於現有之區塊式快速傅立葉轉換乘法演算法，本論文所提出之方法可減少快速傅立葉轉換、點對點乘法以及快速傅立葉反轉換的運算次數，及降低總運算複雜度。

Cloud computing has become increasingly popular in recently years. When users send data to cloud servers for computing, the problem arises is how to ensure the security of the information stored in remote servers. Fully homomorphic encryption (FHE) allows direct operations on encrypted data and has attracted much attention for secured cloud computing. However, the overall system performance is limited by the underlying algorithms which demand extremely complicated arithmetic operations, especially for those with very large operands. Block- and FFT-based (BFFT-based) multiplication algorithm requires less hardware resources for large integer multiplication. With the increased number of blocks, more additions and multiplications are required. Therefore, exploring a low-complexity FFT-based multiplication algorithm for large numbers becomes an alternative and possibly feasible solution for FHE applications.
This thesis presents a low-complexity block- and FFT-based multiplication algorithm. The proposed algorithm treats the zero-padding of even and odd blocks in different ways such that the cross multiplication between even and odd blocks can be obtained by combined block which simply add the correspondent FFT results of odd and even blocks together. Finally, the multiplication result of two large numbers is obtained by accumulating IFFT results of the three kinds of blocks and resolving the carries. Furthermore, the required storage space in the accumulation step is also reduced by rearrange the order of blocks. Compared to related works, the proposed one decreases the number of required FFT, pointwise multiplication and IFFT operations, thus reducing the overall computational complexity.

[1] R. Rivest, L. Adleman, and M. Dertouzos, “On data banks and privacy homomorphisms,” in Foundations of secure computation , 1978, pp. 169-180.
[2] R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, pp. 120-126, Feb. 1978.
[3] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proc. Advances in cryptology, ser. LNCS, 1999, pp. 223-238.
[4] T. ELGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Information Theory, vol. 31, no. 4, pp. 469-472, July 1985.
[5] D. Boneh, E.J. Goh, and K. Nissim, “Evaluating 2-DNF formulas on ciphertexts,” in Proc. Theory of Cryptography, ser. LNCS, 2005, pp. 325-341.
[6] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in STOC, 2009, pp. 169-178.
[7] C. Gentry and S. Halevi, “Implementing Gentry’s fully-homomorphic encryption scheme,” in Proc. Advances in cryptology, ser. LNCS, 2011, pp. 129-148.
[8] M. v. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” in Proc. Advances in cryptology, ser. LNCS, 2010, pp.24-43.
[9] J.S. Coron, A. Mandal, D. Naccache, and M. Tibouchi, “Fully homomorphic encryption over the integers with shorter public keys,” in Proc. Advances in cryptology, ser. LNCS, 2011, pp. 487-504.
[10] J.S. Coron, D. Naccache, and M. Tibouchi, “Public key compression and modulus switching for fully homomorphic encryption over the integers,” in Proc. Advances in cryptology, ser. LNCS, 2012, pp. 446-464.
[11] A. Schönhage and V. Strassen, “Schnelle multiplikation großer Zahlen,” Comput., vol. 7, no. 3, pp. 281-292, 1971.
[12] L. C. C. García, “Can Schönhage multiplication speed up the RSA decryption or encryption?,” University of Technology, Darmstadt, 2005.
[13] W. Wang, Y. Hu, L. Chen, X. Huang, and B. Sunar, “Accelerating fully homomorphic encryption using GPU,” in Proc. IEEE High Performance Extreme Computing(HPEC), 2012, pp.1-5.
[14] X. Cao and C. Moore, “New integer-FFT multiplication architectures and implementations for accelerating fully homomorphic encryption,” IACR Cryptology ePrint Archive, 2013, pp.1-28.
[15] X. Cao, C. Moore, M. O’Neill, E. O’Sullivan, and N. Hanley, “Optimised multiplication architectures for accelerating fully homomorphic encryption,” IEEE Trans. Comput., vol., no., pp., PrePrints, 2015.
[16] Z. Brakerski and V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) LWE,” in Proc. IEEE 52nd Annual Symp. on Foundations of Computer Science(FOCS), 2011, pp.97-106.
[17] A. Karatsuba and Y. Ofman, “Multiplication of many-digital numbers by automatic computers,” in Proc. USSR, 1962, pp.293-294.
[18] D. Knuth, “The Art of Computer Programming,” vol. 2. Reading, MA, USA: Addision-Wesley, 2006.
[19] J.M. Pollard, “The fast Fourier transform in a finite field,” Math. Computation, vol. 25, pp.365-374, Apr. 1971.
[20] N. Emmart and C. Weems, “High precision integer multiplication with a GPU using Strassen’s algorithm with multiple FFT sizes,” Parallel Process. Lett., vol. 21, no.3, pp.359-375, Jul. 2011.
[21] W. Wang, X. Huang, N. Emmart, and C. Weems, “VLSI design of a large-number multiplier for fully homomorphic encryption,” IEEE Trans. Very Large Scale Integer. (VLSI) Syst., vol. 22, no. 9, pp.1879-1887, Sept. 2014.
[22] J.A. Solinas, “Generalized mersenne numbers,” Faculty of Mathematics, University of Waterloo, 1999.
[23] P. Barrett, “Implementing the Rivest, Shamir and Adleman public key encryption algorithm on a standard digital signal processor,” in Proc. Advances in cryptology, ser. LNCS, 1986, pp.311-323.