由於雲端運算(Cloud computing)的快速成長，資訊安全已成為重要的研究主題之一。全同態加密(Fully homomorphic encryption)可直接對密文在第三方伺服器中進行運算以確保原始資料的隱密性。在同態加密運算中，同態乘法運算相較於同態加法運算有較長的運算時間，且在同態乘法運算後需要有額外的雜訊處理運算，進而造成整體同態函數運算時間增加。由於AND邏輯函數及XOR邏輯函數分別相當於同態乘法運算及同態加法運算，因此發展積之互斥和表示式(Exclusive-or sum-of-products)的邏輯最佳化演算法在全同態加密是一個重要的課題。
本論文基於謝爾賓斯基三角形(Sierpinski gasket)與其操作規則所提出的確切積之互斥和邏輯最佳化演算法可減少乘積項(product terms)中兩輸入的AND邏輯閘數目，並以最大次數(Maximal degree)為主要成本考量。評估結果亦顯示，藉由討論配對問題(Matching problem)所選擇的兩個乘機項順序並不會影響到最後的化簡結果。另外，本論文提出後處理的積之互斥和最小化演算法(Post-processing ESOP minimization)可進一步減少運算資源，首先使用負優先(Negative priority)來產生擁有較多正極性的新乘積項，其次使用奇數判斷(Odd detection)來避免效果不大的操作，最後結合傳統最小化演算法來降低更多的運算資源。實驗結果顯示，以四個變數的所有函數內，相較於傳統最小演法，約有23%的函數是可再利用本論文所提的演算法做邏輯化簡，當推論到更多變數的函數下，可再做更多的邏輯化簡。

關鍵字:同態加密、積之互斥和、邏輯最佳化

With the rapid increase in cloud computing applications, the security issue has become an important research topic. Fully homomorphic encryption can allow direct operations with encrypted data in untrusted servers to ensure data privacy. In comparison with homomorphic addition, homomorphic multiplication has a longer computational time. An additional noise management computation is required after performing homomorphic multiplication resulting in extreme computational time of homomorphic evaluation. The AND and XOR Boolean function are equivalent to the homomorphic multiplication and addition, respectively. Therefore, developing a logic optimization of Exclusive-or sum-of-products (ESOP) expression is an important topic in fully homomorphic encryption.
In this thesis, an exact ESOP minimization algorithm based on Sierpinski gasket and manipulation rules is proposed to reduce the numbers of equivalent 2-input AND gates of product term. The primary cost function is to minimize the maximum degree of ESOP. The chosen order of pairs of product terms does not affected the minimization result according to the discussion of the matching problem. Moreover, the proposed post-processing ESOP minimization algorithm can be applied to further reduce the computing resources. First, using the negative priority scheme to produce the new terms in more positive form. Second, using the odd detection scheme to avoid the insignificant operations. Finally, combining the classic minimization to reduce the computing resources.
Experimental results show that about 23% of all 4-variables functions can be further optimized with the proposed algorithm compared with the results of applying the classic minimization. When dealing with functions with more input variables, the proposed one still outperforms the conventional minimization algorithm.

Keywords: Homomorphic encryption; Exclusive-or Sum-of-Products; Logic Optimization

[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, Jul. 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 Proc. 41st Annu. ACM symp. on Theory of Computing(STOC), 2009, pp. 169-178.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] Z. Brakerski, "Fully homomorphic encryption without modulus switching from classical GapSVP," in Proc. Advances in cryptology, ser. LNCS, 2012, pp. 868-886.
[12] 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.
[13] J.S. Coron, T. Lepoint, and M. Tibouchi, "Scale-invariant fully homomorphic encryption over the integers," in Proc. Public-Key Cryptography, ser. LNCS, 2014. 311-328.
[14] A. Mishchenko and M. Perkowski, “Fast heuristic minimization of exclusive-sums-of-products,” in Proc. Reed-Muller Workshop, 2001, pp. 242-250.
[15] T. Kozlowski, E.L. Dagless, and J.M. Saul, “An enhanced algorithm for the minimization of exclusive-OR sum-of-products for incompletely specified functions,” in Proc. IEEE International Conference on Computer Design: VLSI in Computers and Processors(ICCD), 1995, pp. 244-249.
[16] T. Sasao, “EXMIN2: a simplified algorithm for exclusive-OR-sum-of-products expressions for multiple-valued-input two-valued-output functions,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 5, pp. 621-632, May. 1993.
[17] M.R. Garey and D.S. Johnson, Computers and Intractability – A Guide to NP Completeness, W.H. Freeman & Co. New York, NY, USA, 1990.
[18] S.J Hong, R.G. Cain, and D.L. Ostapko, “Mini: a heuristic approach for logic minimization,” IBM Journal of Research and Development, vol. 18, no. 5, pp. 433-458, Sep. 1974.
[19] R. Rudell and A. Sangiovanni-Vincentelli, “Espresso-MV: algorithms for multiple-valued logic minimization,” in Proc. IEEE Custom Integrated Circuits Conference, 1985, pp. 230-234.
[20] D.V. Popel and A. Dani, “Sierpinski gaskets for logic functions representation,” in Proc. IEEE Int. Symp. on Multiple-Valued Logic(ISMVL), 2002, pp. 39-45.
[21] W. Sierpinski, “On a curve every point of which is a point of ramification,” Prace Mat. Fiz., 27, pp. 77-86, 1916.