全同態加密(Fully homomorphic encryption, FHE)是一個對未解密的密文直接運算並確保其安全性的方法，如此即便在雲端上直接對資料做運算也可以確保隱密性。而在實際應用上最大的瓶頸來自於其極高的運算複雜度。本論文針對為解決抑制雜訊的密鑰交換(key-switching) 進行優化，我們將其與基底擴展(base extension)結合，並利用商數預估的方法使其省去餘數與二進位數之間不必要的轉換，大幅降低運算複雜度。此外利用BGV-FHE的特性，更進一步化簡基底轉換的運算，幾乎省下所有商數預估所需的運算。我們還提出更適用於密鑰交換的基底轉換，使AT在各種狀況都可以有顯著的降低，最後以共享硬體運算區塊，提供平行處理更彈性的選擇。由實驗及分析結果顯示，本論文所提出的方法比原始的密鑰交換快了至少2.28倍的速度，並在大部分的參數下獲得7倍以上的加速，至多達到了11.55倍。

Fully homomorphic encryption (FHE) is a theorem of directly computing the encrypted ciphertext and ensuring its security. Therefore, even if the data is computed directly on the cloud, privacy can be guaranteed. The major bottleneck in practical applications comes from its exceptionally high computational complexity. This thesis is focused on key-switching to solve noise suppression. When we combine it with the base extension algorithm and use the quotient estimation method to eliminate the conversion between remainder and binary numbers, it reduces computational complexity tremendously. In addition, using the characteristics of BGV-FHE, the operations of base extension are further simplified, almost saving all the calculations required for quotient estimation. We also propose a base extension that is more suitable for key-switching, reducing AT products significantly in various situations. And the shared hardware calculation block provides more flexible options for parallel processing. The results of experiments and analysis show that the method proposed in this paper is at least 3.7 times faster than the original key-switching. Furthermore, the method achieves a speedup of more than 7 times under most parameters, reaching 12.37 times at most.

[1] R. L. Rivest, L. Adleman, M. L. Dertouzos, et al., “On data banks and privacy homomorphisms,” Foundations of secure computation, vol. 4, no. 11, pp. 169-180, 1978.
[2] T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete　Logarithms”, Advances in Cryptology-CRYPTO'84, Springer-Verlag, LNCS 196,　pp.10-18, 1985
[3] C. Gentry, “Fully homomorphic encryption using ideal lattices,” in Proc. 41st Annu. ACM STOC, pp. 169-178, 2009.
[4] C. Gentry, A fully homomorphic encryption scheme, vol. 20. Stanford University Stanford,2009.
[5] 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.
[6] C. Gentry, S. Halevi, and N. Smart, “Homomorphic evaluation of the AES circuit,” in Proc. CRYPTO, 2012.
[7] Ho, T.Truan, and C. Chang. “Accelerating residue-to-binary conversion of very high cardinality moduli set for fully homomorphic encryption. ” IEEE Asia Pacific Conference on Circuits and Systems (APCCAS). IEEE, pp9-12, 2016.
[8] S. Halevi and V. Shoup, “Helib,” Retrieved from HELib: https://github. com.shaih/HElib, 2014.
[9] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping,” in Proc. 3rd Innovations in Theoretical Computer Science(ITCS), 2012, pp. 309-325.
[10] W. Wang, Z. Chen, and X. Huang, “Accelerating leveled fully homomorphic encryption using GPU,” in Proc. 2014 IEEE Int. Symp. on Circuits and Syst., pp. 2800-2803, 2014.
[11] Jung, Wonkyung, et al. "HEAAN Demystified: Accelerating Fully Homomorphic Encryption Through Architecture-centric Analysis and Optimization." arXiv preprint arXiv:2003.04510, pp.1-14, 2020.
[12] J. W. Cooley and J. W. Tukey, “An Algorithm for the MachineCalculation of Complex Fourier Series,” Mathematics of computation, vol. 19, no. 90, 1965.
[13] A. P. SHENOY and R. KUMARESAN “Fast Base Extension Using a Redundant Modulus in RNS”, IEEE Transactions on Computers Volume.38, Issue: 2, 1989.
[14] E. D. Pitchika and S. Bharadwaj, "Fast Base Extension using Single Redundant Modulus in a Residue Number System," 2019 International Conference on Power Electronics, Control and Automation (ICPECA), pp. 1-5, 2019.
[15] Barrett, Paul. “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. ” Conference on the Theory and Application of Cryptographic Techniques. Springer, pp. 311-323, 1986.
[16] W. Wang, Z. Chen and X. Huang, "Accelerating leveled fully homomorphic encryption using GPU," 2014 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2800-2803, 2014.
[17] H. K. Garg and H. Xiao, "New residue arithmetic based Barrett algorithms: Modular polynomial computations," 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1178-1182,2017.