全同態加密(Fully homomorphic encryption, FHE)是一個新興的加密技術，能在第三方的伺服器中直接對加密的資料進行運算以確保原始資料的隱密性。儘管全同態加密技術在雲端運算的應用中占有極大的重要性，以目前提出的演算法來實現仍需非常高的計算複雜度和硬體成本。同態AES可視為一個複雜的運算函數，現今被提出的同態AES方案皆需龐大的計算時間，其中最花時間的部分是金鑰交換(key-switching)運算，在每一次同態乘法運算、自同構(automorphism)運算後皆會需要進行金鑰交換運算。
本論文提出平行化的SubByte和MixColumn/ShiftRow演算法，主要是透過在關鍵運算路徑上降低同態乘法運算和自同構運算的資料相依性，使其在高平行度的程序下運算能減少同態AES的運算時間。在平行處理下，相較於傳統的同態AES演算法，所提出的演算法可以使同態AES一回合中減少3次金鑰交換運算時間。此外，本論文也基於不同的安全性考量下，提出各個高效能的同態AES硬體架構, 所提出的硬體架構相較於現有的同態AES方案上有著較少的運算時間及更高的效能。

Fully homomorphic encryption (FHE) is an emerging technique that allows the encrypted data to be processed directly in untrusted servers for ensuring data privacy. Despite of the important feature of FHE in cloud computing applications, there are still extremely high computation complexity and implementation cost in the underlying algorithms. Homomorphic evaluation of advanced encryption standard (AES) can be regarded as a complex function, in which existing homomorphic AES implementations still demand a significant amount of computational time. The most expensive operation in homomorphic AES is key switching after homomorphic multiplication and automorphism operations.
To improve the performance of homomorphic AES by reducing homomorphic multiplication and automorphism operations in critical computational paths, this thesis proposes a parallel SubByte and MixColumn/ShiftRow algorithm by relaxing the underlying data dependency. Compared to the conventional homomorphic AES, the proposed one can reduce 3 key switching operations in one round of homomorphic AES assuming parallel processing. Moreover, high-performance hardware architectures of homomorphic AES are presented for different security levels. Performance evaluations show that the proposed design outperforms the related works in terms of computational time and performance.

[1] O. Abdelfattah, "Data conversion in residue number system," department of electrical & computer engineering in McGill University, Jan. 2011.
[2] 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.
[3] 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.
[4] Z. Brakerski, "Fully homomorphic encryption without modulus switching from classical GapSVP," in Proc. Advances in cryptology, ser. LNCS, 2012, pp. 868-886.
[5] Z. Brakerski and V. Vaikuntanathan, "Fully homomorphic encryption from ring-LWE and security for key dependent messages," in Proc. Advances in cryptology, ser. LNCS, 2011, pp. 505-524.
[6] 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.
[7] Y. Doröz, Y. Hu, and B. Sunar, "Homomorphic AES evaluation using the modified LTV scheme," Designs, Codes and Cryptography, vol. 80, no. 2, pp. 333-358, Aug. 2016.
[8] W. Dai, Y. Doröz, and B. Sunar, "Accelerating NTRU based homomorphic encryption using GPUs," in Proc. IEEE Conference on High Performance Extreme Computing (HPEC) 2014, pp. 1-6.
[9] T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," in Proc. Advances in cryptology, ser. LNCS, 1985, pp. 10-18.
[10] 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, 2013, pp. 75-92.
[11] C. Gentry, S. Halevi, and N.P. Smart, "Fully homomorphic encryption with polylog overhead," in Proc. Advances in Cryptology, ser. LNCS, 2012, pp. 465-482.
[12] C. Gentry, S. Halevi, and N.P. Smart, "Homomorphic evaluation of the AES circuit," in Proc. Advances in Cryptology, ser. LNCS, 2012, pp. 850-867.
[13] C. Gentry and S. Halevi, "Implementing Gentry's fully-homomorphic encryption scheme," in Proc. Advances in Cryptology, ser. LNCS, 2011, pp. 129-148.
[14] C. Gentry, S. Halevi, and N.P. Smart, "Better bootstrapping in fully homomorphic encryption," in Proc. Public Key Cryptography, ser. LNCS, 2012, pp. 1-16.
[15] C. Gentry, "Fully homomorphic encryption using ideal lattices," in Proc. 41st Annu. ACM symp. on Theory of Computing(STOC), 2009, pp. 169-178.
[16] S. Goldwasser and S. Micali, "Probabilistic encryption," Journal of computer and system sciences, vol.28, no.2, pp. 270-299, Apr. 1984.
[17] S. Halevi and V. Shoup, "Bootstrapping for HElib," in Proc. Advances in Cryptology, ser. LNCS, 2015, pp. 641-670.
[18] S. He and M. Torkelson, "A new approach to pipeline FFT processor," in Proc. IEEE Conference on Parallel Processing Symposium. 1996, pp. 766-770.
[19] W.J. Lu, “Ring-Learning with errors & HElib,” ppt slide, 2015. Available at https://www.slideshare.net/ssuser4c5f79/h-elib.
[20] V. Lyubashevsky, C. Peikert, and O. Regev, "On ideal lattices and learning with errors over rings," in Proc. Advances in Cryptology, ser. LNCS, 2010, pp. 1-23.
[21] A. López-Alt, E. Tromer, and V. Vaikuntanathan, "On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption," in Proc. 44st Annu. ACM symp. on Theory of Computing(STOC), 2012, pp. 1219-1234.
[22] S. Murphy and M. J.B. Robshaw, "Essential algebraic structure within the AES," in Proc. Advances in Cryptology, ser. LNCS, 2002, pp. 1-16.
[23] K. Lauter, M. Naehrig, and V. Vaikuntanathan, "Can homomorphic encryption be practical?," in Proc. 3rd ACM workshop on Cloud computing security workshop, 2011, pp. 113-124.
[24] E. Öztürk, Y. Doröz, E. Savaş, and B. Sunar, "A custom accelerator for Homomorphic encryption applications," IEEE Transactions Comput., vol. 66, no. 1, pp. 3-16, Jan. 2017.
[25] R. L. Rivest, L. Adleman, and M.L. Dertouzos, "On the data banks and privacy homomorphisms, " in Foundations of secure computation, 1978, pp. 169-180.
[26] N.P. Smart and F. Vercauteren, "Fully homomorphic SIMD operations," Designs, codes and cryptography, vol. 71, no. 1, pp. 57-81, Apr. 2014.
[27] N.P. Smart and F. Vercauteren, "Fully Homomorphic encryption with relatively small key and ciphertext sizes," in Proc. Public Key Cryptography, ser. LNCS, 2010, pp. 420-443.
[28] Y. Wang, "Residue-to-binary converters based on new Chinese remainder theorems," IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 47, no. 3, pp. 197-205, Mar. 2000.