全同態加密(Fully homomorphic encryption, FHE)能讓加密資料在未解密的情況下直接進行運算。這使得即使在雲端上仍能確保資料隱密性。目前來說加密資料的運算需要極高的運算複雜度。我們在本論文中提出在全同態加密資料上的低複雜度比較及交換、二進位加法、以及二進位乘法運算。為了改進這些全同態加密資料的運算效能，我們引用了聚合明文(aggregate plaintext)的概念。我們使用聚合明文的特性設計出更有效的演算法來完成運算，使其可以減少所需的同態運算數量。分析的結果顯示，我們設計的演算法可以將比較及交換、二進位加法、以及二進位乘法所需的同態乘法數量分別降低至lg n+4、2n-1、以及6n-4。此外，對於全同態加密資料的64位元比較及交換和加法，我們所提出的演算法比其他的方法分別快了16及9倍以上，而在32位元乘法上可以加快至7倍以上。

Fully homomorphic encryption (FHE) allows computations to be performed directly on encrypted data. This ensures data privacy even on the cloud. Currently used computations on encrypted data are of extremely high complexity. In this paper, we propose low-complexity low-level operations on fully homomorphic encrypted data such as compare-and-swap, binary addition, and binary multiplication. To improve the algorithmic performance, we apply the concept of aggregate plaintext. The number of homomorphic multiplications in our compare-and-swap, binary addition, and binary multiplication are lg n+4, 2n-1, and 6n-4, respectively. For 64-bit data compare-and-swap and binary addition, the proposed algorithms operate over 16 and 9 times faster than related works, respectively. For 32-bit multiplication, the speed improvement is over 7 times.

[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] C. Gentry, A fully homomorphic encryption scheme, vol. 20. Stanford University Stan- ford, 2009.
[3] C. Gentry and S. Halevi, “Implementing Gentry’s fully homomorphic encryption scheme,” in Annual international conference on the theory and applications of cryptographic techniques, pp. 129–148, Springer, 2011.
[4] S. Halevi, “Homomorphic encryption,” in Tutorials on the Foundations of Cryptography, pp. 219–276, Springer, 2017.
[5] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti, “A survey on homomorphic encryption schemes: Theory and implementation,” ACM Computing Surveys (CSUR), vol. 51, no. 4, p. 79, 2018.
[6] 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.
[7] M. Togan and C. Pleşca, “Comparison-based computations over fully homomorphic encrypted data,” in 2014 10th International Conference on Communications (COMM), pp. 1–6, IEEE, 2014.
[8] M. Togan, “A FHE-based evaluation for searching on encrypted data,” in 2016 International Conference on Communications (COMM), pp. 291–296, IEEE, 2016.
[9] G.S.Çetin,Y.Doröz,B.Sunar,and E.Savaş,“Depthoptimizedefficienthomomorphic sorting,” in International Conference on Cryptology and Information Security in Latin America, pp. 61–80, Springer, 2015.
[10] H. Narumanchi, D. Goyal, N. Emmadi, and P. Gauravaram, “Performance analysis of sorting of FHE data: integer-wise comparison vs bit-wise comparison,” in 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA), pp. 902–908, IEEE, 2017.
[11] J. L. Crawford, C. Gentry, S. Halevi, D. Platt, and V. Shoup, “Doing real work with FHE: The case of logistic regression,” in Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pp. 1–12, ACM, 2018.
[12] J.-H.Ye,S.-Q.Chen,andM.-D.Shieh,“MinimizingESOPexpressionsforfullyhomo- morphic encryption,” in 2018 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1–4, IEEE, 2018.
54
[13] J.-N. Ji and M.-D. Shieh, “Efficient comparison and swap on fully homomorphic encrypted data,” in 2019 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1–4, IEEE, 2019.
[14] N.P.SmartandF.Vercauteren,“FullyhomomorphicSIMDoperations,”Designs, codes and cryptography, vol. 71, no. 1, pp. 57–81, 2014.
[15] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(leveled) fully homomorphic encryption without bootstrapping,” ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3, p. 13, 2014.
[16] V. Lyubashevsky, C. Peikert, and O. Regev, “On ideal lattices and learning with errors over rings,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 1–23, Springer, 2010.
[17] C. Gentry, S. Halevi, and N. P. Smart, “Homomorphic evaluation of the AES circuit,” in Annual Cryptology Conference, pp. 850–867, Springer, 2012.
[18] C. Gentry, S. Halevi, and N. P. Smart, “Fully homomorphic encryption with polylog overhead,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 465–482, Springer, 2012.
[19] S. Halevi and V. Shoup, “Helib,” Retrieved from HELib: https://github. com. shaih/HElib, 2014.
[20] S. Halevi and V. Shoup, “Algorithms in HElib,” in Annual Cryptology Conference, pp. 554–571, Springer, 2014.
[21] S.HaleviandV.Shoup,“BootstrappingforHElib,”inAnnualInternationalconference on the theory and applications of cryptographic techniques, pp. 641–670, Springer, 2015.